SDUT 2019 Autumn Team Contest 17th
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 i4i4. 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 < 231231 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 369Hint
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.这个题自己研究了好久，加起来差不多7个小时，还好最终AC了，努力没有白费，每天进步一点点。加油！
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=2147493647; //一直WA的原因是这里，int表示的最大值是2147483647 //所以爆掉了，全代码应该用long long struct Matrix { ll a[7][7]; }; Matrix mul(Matrix A,Matrix B) { Matrix C= {0,0,0,0,0,0,0, 0,0,0,0,0,0,0, 0,0,0,0,0,0,0, 0,0,0,0,0,0,0, 0,0,0,0,0,0,0, 0,0,0,0,0,0,0, 0,0,0,0,0,0,0, }; ll i,j,k; for(i=0; i<7; i++) { for(j=0; j<7; j++) { for(k=0; k<7; k++) { C.a[i][j]+=A.a[i][k]*B.a[k][j]; C.a[i][j]%=mod; } } } return C; } //Matrix mul(Matrix a,Matrix b) //{ // Matrix s; // mem(s.a,0); // for(ll i=0;i<7;i++) // { // for(ll j=0;j<7;j++) // { // for(ll k=0;k<7;k++) // { // s.a[i][j]+=a.a[i][k]*b.a[k][j]; s.a[i][j]%=mod; // } // } // } // return s; //} void puts(Matrix A) { ll i,j; for(i=0; i<7; i++) { for(j=0; j<7; j++) { cout<<" "<<A.a[i][j]; } cout<<endl; } cout<<endl; } Matrix ksm(Matrix I,ll J) { Matrix ANS= {1,0,0,0,0,0,0, 0,1,0,0,0,0,0, 0,0,1,0,0,0,0, 0,0,0,1,0,0,0, 0,0,0,0,1,0,0, 0,0,0,0,0,1,0, 0,0,0,0,0,0,1, }; while(J) { if(J&1) { ANS=mul(ANS,I); } I=mul(I,I); J>>=1; } return ANS; } int main() { ll t; cin>>t; while(t--) { ll n,x,y; cin>>n>>x>>y; if(n==1) cout<<x<<endl; else if(n==2) cout<<y<<endl; else { n=n-2; Matrix state= { 0,1,0,0,0,0,0, 2,1,1,4,6,4,1, 0,0,1,4,6,4,1, 0,0,0,1,3,3,1, 0,0,0,0,1,2,1, 0,0,0,0,0,1,1, 0,0,0,0,0,0,1, }; Matrix mid=ksm(state,n); Matrix A= {x,0,0,0,0,0,0, y,0,0,0,0,0,0, 16,0,0,0,0,0,0, 8,0,0,0,0,0,0, 4,0,0,0,0,0,0, 2,0,0,0,0,0,0, 1,0,0,0,0,0,0, }; Matrix E; // puts(mid); // puts(A); E=mul(mid,A); // puts(E); cout<<E.a[1][0]<<endl; } } return 0; } //为了更好的理解，可以先去看看矩阵快速幂
