这是一道数学题，，刚开始有点吓人。。表面上看没啥思路，于是就是试着写了几个，发现f(n)=a^fib(n-1)*b^fib(n),n>=2，嘿嘿，这下有了
然而今晚状态真是差的一塌糊涂，各种错误+各种NC思路。。。哎，不多说，拙计。。。。
求a^fib(n)%mod,mod=10^9+7，由于mod是一个大质数，根据费马小定理，a^(mod-1)=1(mod m)，所以a^x有一个循环节，这个循环节为10^9+6
然后就求fib(n)%(mod-1)，用矩阵快速幂即可。接下来求a^x用折半快速幂即可。。。其中，由于a,b,n可以去到0,1，在这之前务必考虑一些特殊情况。。。附代码：#include <iostream>#include <cstdio>#include <vector> #define N 32767#define cl(a) memset(a,0,sizeof(a))#define mod 1000000007#define pb push_back#define ll __int64#define ss(a) scanf("%d",&a)using namespace std;ll f[3][3],f1[3][3],z[3];ll js(ll n,int k){ll res=1,t=n;while (k>0){if (k&1) res=(res*t)%mod;t=(t*t)%mod;k>>=1;}return res;}void init(){cl(z);cl(f);z[1]=1;z[2]=0;f[1][1]=1;f[1][2]=1;f[2][1]=1;f[2][2]=0; }void rmul(){int i,j,k;for (i=1;i<=2;i++)for (j=1;j<=2;j++){f1[i][j]=0;for (k=1;k<=2;k++) f1[i][j]=(f1[i][j]+f[i][k]*f[k][j])%(mod-1);}for (i=1;i<=2;i++)for (j=1;j<=2;j++) f[i][j]=f1[i][j];}void zmul(){ll z1,z2;z1=(f[1][1]*z[1]+f[1][2]*z[2])%(mod-1);z2=(f[2][1]*z[1]+f[2][2]*z[2])%(mod-1);z[1]=z1;z[2]=z2;}ll fib(int n){int i;init();n–;if (n&1) zmul();n>>=1;for (i=1;i<N;i++){rmul();if (n&1) zmul();n>>=1;if (!n) break;}return z[1]; }int main(){int n,a1,b1;while (ss(a1)!=EOF){ss(b1);ss(n);if (n<2){if (!n) cout<<a1%mod<<endl;else cout<<b1%mod<<endl;continue;}if (!a1||!b1){cout<<0<<endl;continue;}int m1,m2;ll res=1;if (a1>1) res=res*js(a1,fib(n-1))%mod;if (b1>1)res=res*js(b1,fib(n))%mod;printf("%d\n",res);}return 0;}
不要再以任何人说你，因为你不是为任何人而活，你只为自己而活，
