HDU5950 Recursive sequence

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

i^{4}

InputThe 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 < $2^{31}$ OutputFor 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
搞了一个7阶的矩阵，跑一遍快速幂就OK了。懒得画矩阵了，和这篇博客里的一样

 1 #include <bits/stdc++.h>
 2 #define N 7
 3 #define mod 2147493647
 4 using namespace std;
 5 typedef long long ll;
 6 struct Mat{
 7     ll a[N][N];
 8     Mat(){
 9         memset(a,0,sizeof(a));
10         a[0][0] = 1,a[0][1] = 2,a[0][2] = 1,a[0][3] = a[0][4] = a[0][5] = a[0][6] = 0;
11         a[1][0] = 1,a[1][1] = a[1][2] = a[1][3] = a[1][4] = a[1][5] = a[1][6] = 0;
12         a[2][2] = 1,a[2][3] = 4,a[2][4] = 6,a[2][5] = 4,a[2][6] = 1;
13         a[3][3] = 1,a[3][4] = a[3][5] = 3,a[3][6] = 1;
14         a[4][4] = a[4][6] = 1,a[4][5] = 2;
15         a[5][5] = a[5][6] = 1;
16         a[6][6] = 1;
17     }
18 };
19 
20 Mat operator * (Mat A,Mat B){
21     Mat ret;
22     for (int i = 0;i < N;++i){
23         for (int j = 0;j < N;++j){
24             ll tmp = 0;
25             for (int k = 0;k < N;++k){
26                 tmp = (tmp + A.a[i][k] * B.a[k][j]) % mod;
27             }
28             ret.a[i][j] = tmp;
29         }
30     }
31     return ret;
32 }
33 
34 Mat operator ^ (Mat A,int n){
35     Mat ret;
36     memset(ret.a,0,sizeof(ret.a));
37     for (int i = 0;i < N;++i) ret.a[i][i] = 1;
38     while(n){
39         if (n&1) ret = ret * A;
40         n >>= 1;
41         A = A*A;
42     }
43     return ret;
44 }
45 
46 int T,n,a,b;
47 
48 int main(){
49     scanf("%d",&T);
50     while(T--){
51         scanf("%d%d%d",&n,&a,&b);
52         if (n == 1){
53             printf("%d
",a%mod);
54             continue;
55         }
56         if (n == 2){
57             printf("%d
",b%mod);
58             continue;
59         }
60         Mat A;
61         A = A ^ (n-2);
62         ll ans = (A.a[0][0] * b % mod+ A.a[0][1] * a % mod + A.a[0][2] * 81 % mod +
63                     A.a[0][3] * 27 % mod + A.a[0][4] * 9 % mod + A.a[0][5] * 3 % mod + A.a[0][6] % mod) % mod;
64         printf("%lld
",ans);
65     }
66     return 0;
67 }