Recursive sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2882 Accepted Submission(s): 1284
Problem Description
Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.
Input
The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.
Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.
Output
For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.
Sample Input
2
3 1 2
4 1 10
Sample Output
85
369
Hint
In the first case, the third number is 85 = 2*1十2十3^4.
In the second case, the third number is 93 = 2*1十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.题意 f[n]=f[n-1]+2*f[n-2]+n^4; f[1]=a f[2]=b 求第n项
解析 直接递推肯定会超时的 所以 构造一个7*7系数矩阵 直接快速幂解出来 由于现在比较菜 只会最简单的矩阵 勉强可以写出来。。。。
1 2 1 0 0 0 0 f[i-1] f[i]
1 0 0 0 0 0 0 f[i-2] f[i-1]
0 0 1 4 6 4 1 i^4 (i+1)^4
0 0 0 1 3 3 1 * i^3 = (i+1)^3
0 0 0 0 1 2 1 i^2 (i+1)^2
0 0 0 0 0 1 1 i i+1
0 0 0 0 0 0 1 1 1
AC代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod=2147493647,maxn=7; 5 struct Matrix 6 { 7 ll m[maxn][maxn]; 8 Matrix() 9 { 10 memset(m,0,sizeof(m)); 11 } 12 void init() 13 { 14 for(int i=0; i<maxn; i++) 15 for(int j=0; j<maxn; j++) 16 m[i][j]=(i==j); 17 } 18 Matrix operator +(const Matrix &b)const 19 { 20 Matrix c; 21 for(int i=0; i<maxn; i++) 22 { 23 for(int j=0; j<maxn; j++) 24 { 25 c.m[i][j]=(m[i][j]+b.m[i][j])%mod; 26 } 27 } 28 return c; 29 } 30 Matrix operator *(const Matrix &b)const 31 { 32 Matrix c; 33 for(int i=0; i<maxn; i++) 34 { 35 for(int j=0; j<maxn; j++) 36 { 37 for(int k=0; k<maxn; k++) 38 { 39 c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%mod)%mod; 40 } 41 } 42 } 43 return c; 44 } 45 Matrix operator^(const ll &t)const 46 { 47 Matrix ans,a=(*this); 48 ans.init(); 49 ll n=t; 50 while(n) 51 { 52 if(n&1) ans=ans*a; 53 a=a*a; 54 n>>=1; 55 } 56 return ans; 57 } 58 }; 59 int main() 60 { 61 int t; 62 ll n,m,a,b; 63 scanf("%d",&t); 64 while(t--) 65 { 66 scanf("%lld %lld %lld",&n,&a,&b); 67 if(n==1) 68 { 69 cout<<a%mod<<endl; 70 continue; 71 } 72 if(n==2) 73 { 74 cout<<b%mod<<endl; 75 continue; 76 } 77 Matrix temp; 78 temp.m[0][0]=1,temp.m[0][1]=2,temp.m[0][2]=1,temp.m[0][3]=0,temp.m[0][4]=0,temp.m[0][5]=0;temp.m[0][6]=0; 79 temp.m[1][0]=1,temp.m[1][1]=0,temp.m[1][2]=0,temp.m[1][3]=0,temp.m[1][4]=0,temp.m[1][5]=0;temp.m[1][6]=0; 80 temp.m[2][0]=0,temp.m[2][1]=0,temp.m[2][2]=1,temp.m[2][3]=4,temp.m[2][4]=6,temp.m[2][5]=4;temp.m[2][6]=1; 81 temp.m[3][0]=0,temp.m[3][1]=0,temp.m[3][2]=0,temp.m[3][3]=1,temp.m[3][4]=3,temp.m[3][5]=3;temp.m[3][6]=1; 82 temp.m[4][0]=0,temp.m[4][1]=0,temp.m[4][2]=0,temp.m[4][3]=0,temp.m[4][4]=1,temp.m[4][5]=2;temp.m[4][6]=1; 83 temp.m[5][0]=0,temp.m[5][1]=0,temp.m[5][2]=0,temp.m[5][3]=0,temp.m[5][4]=0,temp.m[5][5]=1;temp.m[5][6]=1; 84 temp.m[6][0]=0,temp.m[6][1]=0,temp.m[6][2]=0,temp.m[6][3]=0,temp.m[6][4]=0,temp.m[6][5]=0;temp.m[6][6]=1; 85 Matrix aa,bb; 86 bb.m[0][0]=b%mod; 87 bb.m[1][0]=a%mod; 88 bb.m[2][0]=81; 89 bb.m[3][0]=27; 90 bb.m[4][0]=9; 91 bb.m[5][0]=3; 92 bb.m[6][0]=1; 93 aa=temp^(n-2); 94 aa=aa*bb; 95 cout<<aa.m[0][0]%mod<<endl; 96 } 97 return 0; 98 }