class="markdown_views prism-atom-one-light"> 题目大意： 求F(F(N)) 0<=N<=10E100 答案对1e9+7取模 这咋求呢，单纯的一个斐波那契数列我们可以用矩阵快速幂来求，但是对于第一层的F（N）我们是需要一个精确值的！咋办？
用到一个性质！
如果我们对斐波那契数列进行取模，那么这个数列就变成了一个周期数列！（不知道周期数列的自己百度）
PS：我不会证明，找数学竞赛党吧
但是定理没有给出T与模数的关系。。。。
咋整？
我们可以暴力求出这个T（计算机最不怕的就是重复计算）
下面是求出T的暴力程序（跑出来好像需要10s） #include #include #define ull unsigned long long using namespace std; const ull mod=1e9+7; ull x=1,y=1; int main() { ull now=2; while(1) { ull tmp=(x+y)%mod; now++; if(y==1&&tmp==1) { printf("%lld",now-2); return 0; } x=y,y=tmp; } }
这就是T了
那么我们对于第一层的F(N)算出来的值，可以%T去求答案
同样的，我们对于第一层的F（N）也可以求一个周期
为 T2=329616。
那么思路就有了
我们对N%T2，值为K
算F（K），值为W
对W%T
输出F（W%T）即可
PS：由于N过大，我们使用字符串读入（就行快速读入一样），边乘10边%T2即可
（别忘了矩阵快速幂哟！） ull mod=329616; scanf("%s",ss); for(int i=0;i*10*1ll%mod+ss[i]-'0')%mod; #include #include #include #define ull unsigned long long using namespace std; char ss[9999]; ull ans[2][3]; ull x[3][3]; ull dx[3][3]; ull p; void cf1() { for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) dx[i][j]=x[i][j],x[i][j]=0; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) { x[i][j]=(x[i][j]+(dx[i][k]*dx[k][j])%p)%p; } return; } void cf2() { for(int i=1;i<=1;i++) for(int j=1;j<=2;j++) dx[i][j]=ans[i][j],ans[i][j]=0; for(int i=1;i<=1;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) { ans[i][j]=(ans[i][j]+(dx[i][k]*x[k][j])%p)%p; } } ull Fast_pow(ull n) { if(n==0) return 0; if(n==1) return 1; if(n==2) return 1; n-=2; memset(ans,0,sizeof(ans)); memset(x,0,sizeof(x)); memset(dx,0,sizeof(dx)); ans[1][1]=1;ans[1][2]=1; x[1][1]=1; x[2][1]=1; x[1][2]=1; while(n) { if(n%2==1) cf2(); cf1(); n/=2; } return ans[1][1]; } void work() { ull k=0; ull mod=329616; scanf("%s",ss); for(int i=0;i<strlen(ss);i++) k=(k*10*1ll%mod+ss[i]-'0')%mod; p=2000000016; ull w=Fast_pow(k); w%=p; p=1e9+7; printf("%lld ",Fast_pow(w)); } int main() { freopen("na.in","r",stdin); freopen("na.out","w",stdout); int t; cin>>t; for(int i=1;i<=t;i++) work(); return 0; }