题意：定义一个函数G(x)，G(x)=F(F(x))，其中F(x)为斐波那契数列的第X项，F(0)=F(1)=1。给定x求G(x)。答案模1e9+7。x<=1e100。         我们可以知道，在x很大的情况下，在模意义下斐波那契会出现循环，我们可以写一个打表程序判断循环节，发现是每2*1e9+16个数循环。这样我们可以求出F(x)在x<=1e100时斐波那契数列的第x项，那么我们如何求G(x)呢？我们可以再打一遍，求出斐波那契数列在模2*1e9+16意义下的循环节，又得到了一个数是329616。于是我们先将x模329616，然后再用矩阵乘法求出在模2*1e9+16的斐波那契数列的第x项，令其为b，然后求在模1e9+7的意义下斐波那契数列的第b项，即为答案。
       #include #include #include using namespace std; #define mo 329616 long long ans[3][3],f[3][3],h[3][3]; long long mod[2]={1000000007,2000000016}; long long a,b,c; int T; void qpower(long long b,int w) { for (;b>0;b>>=1) { if (b&1) { memset(h,0,sizeof h); for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) for (int k=1;k<=2;k++) h[i][j]=(h[i][j]+ans[i][k]*f[k][j])%mod[w]; memcpy(ans,h,sizeof h); } memset(h,0,sizeof h); for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) for (int k=1;k<=2;k++) h[i][j]=(h[i][j]+f[i][k]*f[k][j])%mod[w]; memcpy(f,h,sizeof h); } } int main() { scanf("%d",&T); while (T--) { char s[1000]; scanf("%s",s); int n=strlen(s); long long x=1; b=0; for (int i=n-1;i>=0;i--) { b=(b+x*(s[i]-'0'))%mo; x=x*10%mo; } ans[2][2]=1;ans[1][1]=ans[1][2]=ans[2][1]=0; f[1][2]=f[2][1]=f[2][2]=1;f[1][1]=0; qpower(b,1); b=ans[2][1]; ans[2][2]=1;ans[1][1]=ans[1][2]=ans[2][1]=0; f[1][2]=f[2][1]=f[2][2]=1;f[1][1]=0; qpower(b,0); printf("%lld ",ans[2][1]); } return 0; }