hdu 5950 Recursive sequence (构造矩阵，快速幂)
题意：
给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。
思路：
很容易想到矩阵，但是i^4不是线性的差评，我们可以拆一下
i^4=(i-1+1)^4,然后二项式展开即可
i^4=(i-1)^4 + 4*(i-1)^3 + 6(i-1)^2 + 4(i-1) + 1
所以为了维护i^4这一项，需要(i-1)^4,(i-1)^3,(i-1)^2,(i-1),1,
再加上f[i-1]和f[i-2]两项，一共7项。
然后构造矩阵为
16沈阳 onsite的题，当时好像写了一个小时，现在看来，果然是个人尽皆知的傻逼题orz
/* ***********************************************
Author :111qqz
Created Time :2017年10月10日 星期二 17时38分11秒
File Name :5950.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=7;
7const LL MOD =2147493647LL;
8LL a,b,n;
9struct Mat
10{
11 LL mat[N][N];
12 void clear()
13 {
14 ms(mat,0);
15 }
16 void print()
17 {
18 for ( int i = 0 ; i < N; i++)
19 for ( int j = 0 ; j < N ; j++)
20 printf("%lld%c",mat[i][j],j==N-1?'\n':' ');
21 puts("");
22 }
23}M,M1;
24Mat operator * (Mat a,Mat b)
25{
26 Mat c;
27 c.clear();
28 for ( int i = 0 ; i < N ; i++)
29 for ( int j = 0 ; j < N ; j++)
30 for ( int k = 0 ; k < N ; k++)
31 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]%MOD)%MOD;
32 return c;
33}
34Mat operator ^ (Mat a,LL b)
35{
36 Mat res;
37 res.clear();
38 for ( int i = 0 ; i < N ; i++) res.mat[i][i] = 1;
39 while (b>0)
40 {
41 if (b&1) res = res * a;
42 b = b >> 1LL;
43 a = a * a;
44 }
45 return res;
46}
47LL solve()
48{
49 M.clear();
50 M.mat[0][1]=M.mat[1][2]=1;
51 for ( int i = 1 ; i < N; i++) M.mat[i][N-1]=1,M.mat[i][i]=1;
52 M.mat[1][0]=M.mat[4][5]=2;
53 M.mat[1][3]=M.mat[1][5]=M.mat[2][3]=M.mat[2][5]=4;
54 M.mat[1][4]=M.mat[2][4]=6;
55 M.mat[3][4]=M.mat[3][5]=3;
56 //M.print();
57 M1.clear();
58 M1.mat[0][0]=a;
59 M1.mat[1][0]=b;
60 //注意下标是从1开始的
61 M1.mat[2][0]=16;
62 M1.mat[3][0]=8;
63 M1.mat[4][0]=4;
64 M1.mat[5][0]=2;
65 M1.mat[6][0]=1;
66 //M1.print();
67 Mat ans;
68 ans.clear();
69 ans = (M^(n-2))*M1;
70 //ans.print();
71 return ans.mat[1][0];
72}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 int T;
7 cin>>T;
8 while (T--)
9 {
10 scanf("%lld%lld%lld",&n,&a,&b);
11 LL ans = solve();
12 printf("%lld\n",ans);
13 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}