首页 > 代码库 > 洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]

洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]

 P1962 斐波那契数列

大家都知道,斐波那契数列是满足如下性质的一个数列:

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式:

 

·第 1 行:一个整数 n

 

输出格式:

 

第 1 行: f(n) mod 1000000007 的值

 

输入输出样例

输入样例#1:
5
输出样例#1:
5
输入样例#2:
10
输出样例#2:
55

说明

对于 60% 的数据: n ≤ 92

对于 100% 的数据: n在long long(INT64)范围内。


 

1 1

1 0

fn+1 fn

fn fn-1

注意n的范围

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int MOD=1e9+7;ll n;struct mat{    ll m[3][3];    mat(){memset(m,0,sizeof(m));}}im,f;void init(){    im.m[1][1]=im.m[2][2]=1;    f.m[1][1]=f.m[1][2]=f.m[2][1]=1;}mat mul(mat &a,mat &b){    mat c;    for(int i=1;i<=2;i++)        for(int k=1;k<=2;k++) if(a.m[i][k])            for(int j=1;j<=2;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD;    return c;}int main(){    scanf("%lld",&n);    init();    mat ans=im;    for(;n;n>>=1,f=mul(f,f))        if(n&1) ans=mul(ans,f);    printf("%d",ans.m[1][2]);}

 

 


 

 P1349 广义斐波那契数列

题目描述

广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q,以及数列的最前两项a1和a2,另给出两个整数n和m,试求数列的第n项an除以m的余数。

输入输出格式

输入格式:

 

输入包含一行6个整数。依次是p,q,a1,a2,n,m,其中在p,q,a1,a2整数范围内,n和m在长整数范围内。

 

输出格式:

 

输出包含一行一个整数,即an除以m的余数。

 

输入输出样例

输入样例#1:
1 1 1 1 10 7
输出样例#1:
6

说明

数列第10项是55,除以7的余数为6。


构造矩阵

p q

1 0

求它的n-2次幂,再乘

a2

a1

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;ll p,q,a1,a2,n,MOD;struct mat{    int r,c;    ll m[3][3];    mat(){r=c=2;memset(m,0,sizeof(m));}}im,f;void init(){    im.m[1][1]=im.m[2][2]=1;    f.m[1][1]=p;f.m[1][2]=q;f.m[2][1]=1;}mat mul(mat &a,mat &b){//printf("p\n");    mat c;    for(int i=1;i<=a.r;i++)        for(int k=1;k<=a.c;k++) if(a.m[i][k])            for(int j=1;j<=b.c;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD;    return c;}int main(){    scanf("%d%d%d%d%lld%lld",&p,&q,&a1,&a2,&n,&MOD);    init();n-=2;    mat ans=im;    for(;n;n>>=1,f=mul(f,f))        if(n&1) ans=mul(ans,f);        //printf("a %d %d %d %d\n",ans.m[1][1],ans.m[1][2],ans.m[2][1],ans.m[2][2]);    mat a;    a.r=2;a.c=1;    a.m[1][1]=a2;a.m[2][1]=a1;    a=mul(ans,a);    printf("%d",a.m[1][1]%MOD);}

 

 

 




 

PS

gcd(fn,fm)=f(gcd(n,m)) 

洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]