Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1498    Accepted Submission(s): 505 Problem Description      Holion August will eat every thing he has found.      Now there are many foods,but he does not want to eat all of them at once,so he find a sequence. fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise      He gives you 5 numbers n,a,b,c,p,and he will eat  fn  foods.But there are only p foods,so you should tell him  fn  mod p.   Input      The first line has a number,T,means testcase.      Each testcase has 5 numbers,including n,a,b,c,p in a line.     1≤T≤10,1≤n≤1018,1≤a,b,c≤109 , p  is a prime number,and  p≤109+7 .   Output      Output one number for each case,which is  fn  mod p.   Sample Input 1 5 3 3 3 233   Sample Output 190   根据题意写成递推式 ，然后可以看出

指数有递推式，可以通过矩阵快速幂来求解。再用下面这公式快速幂取模即可。

（C是素数）

C是素数所以   x只需要对(C-1) 取模就行了

对于指数 ， 求可以得到递推式 f1=0; f2=b; f3=c*b; f(n)=c*f(n-1)+f(n-2)+b; /* | c 1 b|    | Fn-1|         | Fn  | | 1 0 0| *  | Fn-2| -》  | Fn-1| | 0 0 1|    | 1      |         | 1   | */

#include<bits/stdc++.h> #define LL long long #define INF 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define bug puts("***********") using namespace std; const int N =510; LL mod,eul; struct Mat{ LL mat[3][3]; }sta,fi; Mat mul(Mat a,Mat b){ Mat c; mem(c.mat,0); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j]%(mod-1))%(mod-1); } } } return c; } Mat quick(Mat a,LL k){ Mat c; mem(c.mat,0); for(int i=0;i<3;i++) c.mat[i][i]=1; while(k){ if(k&1) c=mul(c,a); a=mul(a,a); k>>=1; } return c; } LL quick(LL a,LL k){ LL ans=1; while(k){ if(k&1)ans=(ans*a)%mod; a=(a*a)%mod; k>>=1; } return ans%mod; } int main(){ int t; // cout<<(LL)pow(201,3)*27*27%233<<endl; // cout<<(LL)pow(220,3)*27*201%233<<endl; scanf("%d",&t); LL n,a,b,c; while(t--){ scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&mod); mem(sta.mat,0); mem(fi.mat,0); LL temp=quick(a,b); fi.mat[2][0]=1; fi.mat[1][0]=temp; fi.mat[0][0]=temp*quick(temp,c)%mod; sta.mat[0][0]=c; sta.mat[0][1]=1; sta.mat[0][2]=b; sta.mat[1][0]=sta.mat[2][2]=1; if(n<=3){ printf("%lld\n",fi.mat[3-n][0]); continue; } // puts("***"); sta=quick(sta,n-2); LL ans=sta.mat[0][0]*b+sta.mat[0][2]; //cout<<fi.mat[0][0]<<endl; ans=quick(a,ans); printf("%lld\n",ans); } return 0; }