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]
/* ***********************************************
Author :111qqz
Created Time :2017年09月30日 星期六 17时47分20秒
File Name :5015.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;
6int n,m;
7int a[15];
8const LL MOD=10000007;
9struct Mat
10{
11 LL mat[15][15];
12 void clear()
13 {
14 ms(mat,0);
15 }
16 void print()
17 {
18 for ( int i = 0 ; i <= n+1 ; i++)
19 {
20 for ( int j = 0 ; j <= n+1 ; j++)
21 {
22 printf("%lld ",mat[i][j]);
23 }
24 printf("\n");
25 }
26 }
27}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 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}