Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：#
给出矩阵的构造规则： 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;
56
57Mat operator * (Mat a,Mat b)
58{
59 Mat c;
60 c.clear();
61 for ( int i = 0 ; i <= n+1 ; i++)
62 for ( int j = 0 ; j <= n+1 ; j++)
63 for ( int k = 0 ; k <= n+1 ; k++)
64 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] )%MOD;
65 return c;
66}
67Mat operator ^ (Mat a,LL b)
68{
69 Mat ret;
70 ret.clear();
71 for ( int i = 0 ; i <= n+1 ; i++) ret.mat[i][i]=1;
72 while (b>0)
73 {
74 if (b&1) ret = ret * a;
75 b = b >> 1LL;
76 a = a * a;
77 }
78 return ret;
79}
80LL solve()
81{
82 M1.clear();
83 M.clear();
84 M1.mat[0][0]=23;
85 M1.mat[n+1][0]=3;
86 for ( int i = 1 ; i <= n ; i++)
87 {
88 M1.mat[i][0] = a[i];
89 }
90 for ( int i = 0 ; i <= n+1 ; i++)
91 {
92 for ( int j = 0 ; j <= n+1; j++)
93 {
94 if (j==0)
95 {
96 if (i!=n+1)
97 M.mat[i][j]=10;
98 }else if (j==n+1)
99 {
100 M.mat[i][j]=1;
101 }else if (i<=n && j>=1&&j<=i)
102 {
103 M.mat[i][j]=1;
104 }
105 }
106 }
107 // M1.print();
108 // M.print();
109 Mat ans;
110 ans.clear();
111 ans = (M^(m))*M1;
112 //ans.print();
113 return ans.mat[n][0];
114}
115
116
117int main()
118{
119 #ifndef ONLINE_JUDGE
120 freopen("./in.txt","r",stdin);
121 #endif
122 while (~scanf("%d %d",&n,&m))
123 {
124 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
125 LL ret = solve()%MOD;
126 printf("%lld\n",ret);
127 }
128
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}