【HDU - 5015 】233 Matrix （矩阵快速幂）

题干：

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 a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got ai,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,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 ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).

Output

For each case, output a n,m mod 10000007.

Sample Input

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

Sample Output

234
2799
72937

Hint

结题报告：

         依旧是按照列，找一个转移矩阵，然后做运算，最后乘上之前保存的数组，得到想要的结果

AC代码：

#include<bits/stdc++.h>

using namespace std;
const int MAX = 20 ;
const int mod = 10000007 ;
struct Matrix {
    long long mat[MAX][MAX];
};
int n,m;
long long b[MAX];
Matrix mul(Matrix a,Matrix b)
{
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=0; i<=n+1; i++) {
        for(int j=0; j<=n+1; j++) {
            c.mat[i][j]=0;
            for(int k=0; k<=n+1; k++) {
                if(a.mat[i][k]&&b.mat[k][j]) {
                    c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];//矩阵乘法
                    c.mat[i][j]%=mod;
                }
            }
        }
    }
    return c;//返回乘完了之后的矩阵
}
Matrix q_pow(Matrix a, int k)
{
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=0;i<=n+1;i++)
        ans.mat[i][i]=1;
    while(k)//使用快速幂的思想进行矩阵的m次方相乘
    {
        if(k&1) {
        	ans=mul(ans,a);
    	}
		k>>=1;
        a=mul(a,a);
    }
    return ans;
}
    
int main()
{
    int m;
    Matrix a;//转移矩阵 
    while(~scanf("%d%d",&n,&m) )
    {
        //初始化第一列 //b数组就是第一列，最后与转移矩阵的m次方相乘得到anm
	    for(int i=1; i<=n; i++) {
	    	scanf("%lld",&b[i]);
		}
	    b[0]=23;
	    b[n+1]=3;
	    //求a这个转移矩阵。先初始化！因为你比如a13 这个地方的值就没有更新到，因为他是0，所以运算之后就可能改变值了，所以下一组输入的时候a13这里就不是0了，所以这里一定要memset一下。 
	    memset(a.mat,0,sizeof(a.mat));
	    for(int i = 0; i<=n; i++) {
	        a.mat[i][0]=10;
	        a.mat[i][n+1]=1;
	    }
	    a.mat[n+1][n+1]=1;
	    for(int i = 1; i<=n; i++) {
	        for(int j = 1; j<=i; j++) {
	            a.mat[i][j]=1;
	        }
	    }
        Matrix end = q_pow(a,m);
        long long ans=0;
        for(int i = 0;i<=n+1;i++) {
        	ans+=(end.mat[n][i]*b[i])%mod,ans%=mod;
		}
        printf("%lld\n",ans);
    }
    return 0;
}