Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2887 Accepted Submission(s): 969
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.
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.
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
Source
1 //https://blog.csdn.net/V5ZSQ/article/details/51302603 2 3 #include <iostream> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstring> 7 #include <string> 8 using namespace std; 9 typedef long long ll; 10 struct ma{ 11 ll m[3][3]; 12 ma() 13 { 14 memset(m,0,sizeof(m)); 15 } 16 }; 17 ma ma_m(ma a,ma b,ll p) 18 { 19 ma c; 20 for(int i=0;i<3;i++) 21 { 22 for(int j=0;j<3;j++) 23 { 24 25 for(int k=0;k<3;k++) 26 { 27 c.m[i][j] = (c.m[i][j]+(a.m[i][k]*b.m[k][j])%p+p)%p; 28 } 29 30 } 31 } 32 return c; 33 } 34 ma ma_q(ma a,ll k,ll p) 35 { 36 ma ret; 37 for(int i=0;i<3;i++) 38 { 39 ret.m[i][i]=1; 40 } 41 while(k) 42 { 43 if(k&1) 44 { 45 ret=ma_m(ret,a,p); 46 } 47 a=ma_m(a,a,p); 48 k>>=1; 49 } 50 return ret; 51 } 52 ll qu(ll a,ll b,ll p) 53 { 54 a%=p; 55 ll ret=1; 56 while(b) 57 { 58 if(b&1) 59 { 60 ret=ret*a%p; 61 } 62 a=a*a%p; 63 b>>=1; 64 } 65 return ret%p; 66 } 67 int main() 68 { 69 ll t; 70 ll n,a,b,c,p; 71 scanf("%lld",&t); 72 while(t--) 73 { 74 scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&c,&p); 75 if(a%p==0) 76 { 77 printf("0 "); 78 } 79 else if(n==1) 80 { 81 printf("1 "); 82 } 83 else if(n==2) 84 { 85 printf("%lld ",qu(a,b,p)); 86 } 87 else { 88 p--; 89 ma aa; 90 aa.m[0][0]=c;aa.m[0][1]=1;aa.m[0][2]=b; 91 aa.m[1][0]=1;aa.m[1][1]=0;aa.m[1][2]=0; 92 aa.m[2][0]=0;aa.m[2][1]=0;aa.m[2][2]=1; 93 aa=ma_q(aa,n-2,p); 94 ll t=aa.m[0][0]*b+aa.m[0][2]; 95 p++; 96 printf("%lld ",qu(a,t,p)); 97 98 } 99 } 100 return 0; 101 }