HDOJ 5015 :233 Matrix

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

这是一道矩阵乘法的题。

首先，我们发现 $n<=10,m<=10^9$ ，这样转移矩阵的大小就应为 $(10^9)^2$ 。
但是，如果我们把行列调换，那么转移矩阵的大小为 $10^2$ 就够了。

然后，我们就只需要构造状态矩阵和转移矩阵就行了。233，2333……的递推就是*10+3。
因为 $f[i][j]=f[i-1][j]+f[i][j-1]$ ,所以我们只须保留一行的状态就行了（注意，行列已调换）。
我们继续分解转移式子：
$f[i][j]=f[i-1][j]+f[i][j-1]=f[i][0]+sum_{k=1}^jf[i-1][k]$ 。
因为第k个位置对第j个位置有1倍的贡献，所以转移矩阵的 $a[k][j]=1$ .

最后，处理一下细节问题。因为2333……的递推需要3，所以我们用类似石头游戏的做法，定义一个数字来源，每次提供3。
我们把行加上1，把状态矩阵的第0个位置设为3，第1个位置表示2333……，剩下的位置表示原来的第0列。关于数字来源和233的转移矩阵，我们要做的是 $a[0][0]=1,a[0][1]=1,a[1][1]=10$ .。

温馨提示：开 $long ~ long$ .
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=15;
const int mod=10000007;
int n,m;
void multself(ll a[N][N])
{
	ll c[N][N];memset(c,0,sizeof(c));
	for(int i=0;i<=n;i++)
		for(int k=0;k<=n;k++)if(a[i][k])
			for(int j=0;j<=n;j++)
				c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
	memcpy(a,c,sizeof(c));
}
void mult(ll f[N],ll a[N][N])
{
	ll c[N];memset(c,0,sizeof(c));
	for(int k=0;k<=n;k++)if(f[k])
		for(int j=0;j<=n;j++)
			c[j]=(c[j]+f[k]*a[k][j])%mod;
	memcpy(f,c,sizeof(c));
}
ll a[N][N],f[N];
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		++n;
		memset(a,0,sizeof(a));
		f[0]=3;f[1]=233;a[0][1]=1;a[1][1]=10;a[0][0]=1;
		for(int i=2;i<=n;i++)
		{
			scanf("%lld",&f[i]);
			for(int j=1;j<=i;j++)a[j][i]=1;
		}
		while(m)
		{
			if(m&1)mult(f,a);
			multself(a);m=m>>1;
		}
		printf("%lld
",f[n]);
	}
	return 0;
}