hdu 5015 233 Matrix (构造矩阵，快速幂)
题意：
给出矩阵的构造规则： a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1)，对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]
现在问a[n][m] 在% 1E7+7 下的值是多少 （n<=10,m<=1E9）
思路：
显然矩阵快速幂，但是不会构造矩阵，放弃。
看了很多题解…发现都是“显然”构造出矩阵。。。似乎是直接凑出来的。。。
可能需要积累一点经验。
对于这道题，我们观察到n很小
所以一个直觉就是从n-1列推到第n列，推到n+1列这样地推。
初始第一列的信息是（假设n为3）
[a1]
[a2]
[a3]
然后我们想要得到
[a1+233]
[a1+a2+233]
[a1+a2+a3+233]
我们发现我们需要233这个常数项体现在矩阵中
而且之后还需要233,2333,23333体现在矩阵中。
那么，我们可以在初始添加23和3两项，这样23…3就都可以构造出来了（我觉得关键点就在这一步，应该是凭借经验吧，虽然刚开始有点难想到orz)
因此现在初始列变成了(其实放置顺序无所谓，不过这样放可以让ai和行数对应，比较友好。
[23]
[a1]
[a2]
[a3]
[3]
设该矩阵为A
现在我们想得到下一列
[233]
[a1+233]
[a1+a2+233]
[a1+a2+a3+233]
[3]
设该矩阵为B
那么现在的问题就是构造一个矩阵5*5的矩阵X,使得X×A=B
凭借直觉（经验？
我们得到这样的矩阵X为
[10,0,0,0,1]
[10,1,0,0,1]
[10,1,1,0,1]
[10,1,1,1,1]
[0, 0,0,0,1]
接下来就是矩阵快速幂了，答案是 (X^m)×A.mat[n][0]
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月30日 星期六 17时47分20秒
4File Name :5015.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34int n,m;
35int a[15];
36const LL MOD=10000007;
37struct Mat
38{
39 LL mat[15][15];
40 void clear()
41 {
42 ms(mat,0);
43 }
44 void print()
45 {
46 for ( int i = 0 ; i <= n+1 ; i++)
47 {
48 for ( int j = 0 ; j <= n+1 ; j++)
49 {
50 printf("%lld ",mat[i][j]);
51 }
52 printf("\n");
53 }
54 }
55}M,M1;
1Mat operator * (Mat a,Mat b)
2{
3 Mat c;
4 c.clear();
5 for ( int i = 0 ; i <= n+1 ; i++)
6 for ( int j = 0 ; j <= n+1 ; j++)
7 for ( int k = 0 ; k <= n+1 ; k++)
8 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] )%MOD;
9 return c;
10}
11Mat operator ^ (Mat a,LL b)
12{
13 Mat ret;
14 ret.clear();
15 for ( int i = 0 ; i <= n+1 ; i++) ret.mat[i][i]=1;
16 while (b>0)
17 {
18 if (b&1) ret = ret * a;
19 b = b >> 1LL;
20 a = a * a;
21 }
22 return ret;
23}
24LL solve()
25{
26 M1.clear();
27 M.clear();
28 M1.mat[0][0]=23;
29 M1.mat[n+1][0]=3;
30 for ( int i = 1 ; i <= n ; i++)
31 {
32 M1.mat[i][0] = a[i];
33 }
34 for ( int i = 0 ; i <= n+1 ; i++)
35 {
36 for ( int j = 0 ; j <= n+1; j++)
37 {
38 if (j==0)
39 {
40 if (i!=n+1)
41 M.mat[i][j]=10;
42 }else if (j==n+1)
43 {
44 M.mat[i][j]=1;
45 }else if (i<=n && j>=1&&j<=i)
46 {
47 M.mat[i][j]=1;
48 }
49 }
50 }
51 // M1.print();
52 // M.print();
53 Mat ans;
54 ans.clear();
55 ans = (M^(m))*M1;
56 //ans.print();
57 return ans.mat[n][0];
58}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 while (~scanf("%d %d",&n,&m))
7 {
8 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
9 LL ret = solve()%MOD;
10 printf("%lld\n",ret);
11 }
12
13 #ifndef ONLINE_JUDGE
14 fclose(stdin);
15 #endif
16 return 0;
17}