利用公式可以通过矩阵快速幂 O(lgn) 的复杂度求出
[f(x)f(x−1)]=[1110]x−2[f(2)f(1)] #include<cstdio> #include<iostream> #include<cstring> #include<cmath> const int MOD=1000000007; using namespace std; typedef long long int LL; struct Matrix { int m[2][2]; void print() { for(int i=0;i<=1;i++) { for(int j=0;j<=1;j++) cout<<m[i][j]<<" "; cout<<endl; } } }; Matrix Mul(Matrix a,Matrix b)//两个矩阵相乘 { Matrix c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) c.m[i][j]+=((a.m[i][k]*b.m[k][j])%MOD+MOD)%MOD; return c; } Matrix Fastm(Matrix a,int n)//求矩阵a的n次幂 { Matrix res; memset(res.m,0,sizeof(res.m)); res.m[0][0]=res.m[1][1]=1;//初始化res为单位矩阵 while(n) { if(n&1)//如果为奇数 res=Mul(res,a); n>>=1; a=Mul(a,a); } return res; } LL fib(int x)//求fib[x]结果取模MOD { if(x==1 || x==2)return 1; Matrix ans; memset(ans.m,0,sizeof(ans.m)); ans.m[0][0]=ans.m[0][1]=ans.m[1][0]=1; ans=Fastm(ans,x-2); return ((ans.m[0][0]*1+ans.m[0][1]*1)%MOD+MOD)%MOD; }