本文共 2138 字，大约阅读时间需要 7 分钟。

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 a i,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 说句实话现在对矩阵快速幂还是不太熟悉。。 这个题有一个突破口就是a[i][j]= a[i-1][j]+a[i][j-1]。通过这一条件去构造矩阵。 我们可以一列一列的去递推这个关系。这是这个题挺玄幻的地方。还有一个就是题干中只给出了a[0][1],a[0][2]等等的值，却没有给出a[0][0]的值。如果a[0][0]=23的话，那岂不是太美了。 假如n=3，m=3 通过这个式子我们就可以得出递推矩阵，进而通过矩阵快速幂来实现。 代码如下：

#include
   
    #define ll long long#define mod 10000007using namespace std;struct Node{
   	ll ans[15][15];};int n,m;inline void clear(Node &ans){
   	for(int i=0;i<=n+1;i++)	{
   		for(int j=0;j<=n+1;j++)		{
   			ans.ans[i][j]=(i==j);		}	}}inline Node operator *(Node &a,Node &b){
   	Node ans;	for(int i=0;i<=n+1;i++)	for(int j=0;j<=n+1;j++) ans.ans[i][j]=0;	for(int k=0;k<=n+1;k++)	{
   		for(int i=0;i<=n+1;i++)		{
   			for(int j=0;j<=n+1;j++)			ans.ans[i][j]=(ans.ans[i][j]+a.ans[i][k]*b.ans[k][j]%mod)%mod;		}	}	return ans;}int main(){
   	while(~scanf("%d%d",&n,&m))	{
   		Node ret;		clear(ret);		Node ans1;		for(int i=0;i<=n+1;i++)		{
   			for(int j=0;j<=n+1;j++)			{
   				if(j==0&&i!=n+1) ans1.ans[i][j]=10;				else if(i!=n+1&&i>0&&i>=j) ans1.ans[i][j]=1;				else if(j==n+1) ans1.ans[i][j]=1;				else ans1.ans[i][j]=0; 			}		}		while(m)		{
   			if(m&1) ret=ret*ans1;			m>>=1;			ans1=ans1*ans1;		}		ll x,ans=23*ret.ans[n][0]%mod;		for(int i=1;i<=n;i++) 		{
   			scanf("%lld",&x);			ans=(ans+x*ret.ans[n][i]%mod)%mod;		}		ans=(ans+3*ret.ans[n][n+1]%mod)%mod;		printf("%lld\n",ans%mod);	}	return 0;}
   

努力加油a啊，(^o)/~

转载地址：http://zztvi.baihongyu.com/