HDU 5015 233 Matrix 【矩阵快速幂】

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5015

——————————————-.

233 Matrix

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1817 Accepted Submission(s): 1075

Problem Description
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 … in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333… (it means a0,1 = 233,a0,2 = 2333,a0,3 = 23333…) Besides, in 233 matrix, we got ai,j = ai-1,j +ai,j-1( i,j ≠ 0). Now you have known a1,0,a2,0,…,an,0, could you tell me an,m in the 233 matrix?

Input
There are multiple test cases. Please process till EOF.

For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 109). The second line contains n integers, a1,0,a2,0,…,an,0(0 ≤ ai,0 < 231).

Output
For each case, output an,m mod 10000007.

Sample Input
1 1
1
2 2
0 0
3 7
23 47 16

Sample Output
234
2799
72937

Hint

—————————————————–.

题目大意 : 这道题 很好读懂 不需要翻译

解题思路:
就是构造矩阵 然后计算a[n][m]的值

我的思路就是
先把a[i][0]都为0的时候a[n][m]的值计算出来
再把a[0][i]都当成0的时候a[n][m]的值计算出来
把两者相加就是最终的结果了

所以我们就把这个问题分成两个子问题做就是了

一、
我先求的是a[0][i]都当成0的时候的a[n][m]值
这个其实很好求 先手写了一下发现有个规律

为了能明确的表达这个规律
在这里我们定义Sni为n个a[i][0]项和 SSni为Sni的前n项和 依此类推
未来了避免书写SSSSni的情况用mSni表示
例如3Sni就是SSSni; 这时候m=0就表示a[i][0]的值

我们通过手写能够知道a[n][m]的值为
(n-1)Smi+(n-2)Smi+…+(n-n)Smi;

而找这些值就很好处理了 只要构造一个上三角矩阵就行了

初始化a[i][j] 使每行都为a[i][0] 在乘上 上三角矩阵的k-1次幂就行了 切记a*上三角 不能反过来 因为矩阵只有结合律没有交换律

这样a[0]