原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=5015
解题思路：一看到题目，感觉是杨辉三角形，然后用组合数学做，不过没想出来怎么做，后来看数据+递推思想，感觉可能是矩阵快速幂，可惜一直不知道a*10+3的 +3怎么处理，果然还是图样图森破啊！如果矩阵能搞出来的话，后面的就简单了，真可惜一直到比赛结束也没想出来，看来这种矩阵的题目做的太少了，真后悔线性代数没有认真学。。
今天晚上又想了一会，完全可以把+3那个放到新的一阶矩阵上，值始终等于3，那么对于233->2333->23333就可以得到矩阵：
1 0
1 10
把这个矩阵和（3,233）相乘就可以得到（3,2333），再乘就得到（3,23333）依次类推。
对于题目中的n，可以构造一个(n+2)*(n+2)的矩阵，可以推出递推矩阵：
1 0 0 0 0.....
1 10 0 0 0...
1 10 1 0 0...
1 10 1 1 0 ...
1 10 1 1 1 ...
前i行的后(i-1)个元素都是0，从第2行开始的每一行的第二个元素都是10，其他都是1。
然后把这个矩阵求p次幂，（用矩阵快速幂）再求出初始向量，最后把向量和刚刚的矩阵快速幂结果相乘，取出结果的最后一个数就是答案啦！
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
using namespace std;
#define N 15
#define M 15
#define K 6
using namespace std;
typedef long long ll;
struct matrix
{
ll m[N][M];
int row,col;
};
matrix A,B,C,ANS;
matrix& matrix_mul(matrix &a,matrix &b,ll p,matrix &ans)//a，b矩阵相乘每个数模p
{
for(int i=;i<a.row;i++)
for(int j=;j<b.col;j++)
ans.m[i][j]=;
ans.row=a.row;
ans.col=b.col;
/*for(int i=0;i<a.row;i++)
for(int j=0;j<a.col;j++)
if(j<a.col-1)
printf("%d ",a.m[i][j]);
else printf("%d\n",a.m[i][j]);
cout<<endl;*/
for(int i=;i<a.row;i++)
for(int k=;k<a.col;k++)
{
for(int j=;j<b.col;j++)
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%p;
}
return ans;
}
void print(matrix& a)
{
printf("->%d %d\n",a.row,a.col);
for(int i=;i<a.row;i++)
for(int j=;j<a.col;j++)
if(j<a.col-)
printf("%d ",a.m[i][j]);
else printf("%d\n",a.m[i][j]);
cout<<endl;
}
matrix z;
matrix &fast_matrixt_mul_mod(matrix &a,int b,ll p,matrix &ans)//矩阵a的b次方模p
{
for(int i=;i<N;i++)
for(int j=;j<M;j++)
if(i==j)ans.m[i][j]=;
else ans.m[i][j]=;
ans.row=a.row;
ans.col=a.col;
//cout<<"=="<<endl;
while(b)
{
if(b&)
{
b--;
ans=matrix_mul(ans,a,p,z);//ans=ans*a%m;
}
else
{
b/=;
a=matrix_mul(a,a,p,z);//a=a*a%m;
}
/*for(int i=0;i<ans.row;i++)
for(int j=0;j<ans.col;j++)
if(j<ans.col-1)
printf("%d ",ans.m[i][j]);
else printf("%d\n",ans.m[i][j]);
cout<<endl;*/
}
return ans;
}
matrix Mat,vec,ans;
#define mod 10000007
int main()
{
int n,p,i,j;
while(scanf("%d%d",&n,&p)!=EOF)
{
vec.row=n+;
vec.col=;
vec.m[][]=;
vec.m[][]=;
for(i=;i<=n+;i++)
{
scanf("%I64d",&vec.m[i][]);
}
Mat.col=Mat.row=n+;
CLR(Mat.m);
for(i=;i<=n+;i++)
{
for(j=;j<=i;j++)
{
if(j!=)Mat.m[i][j]=;
else Mat.m[i][j]=;
}
}
//print(Mat);
fast_matrixt_mul_mod(Mat,p,mod,ans);
matrix_mul(ans,vec,mod,Mat);
//print(Mat);
printf("%I64d\n",Mat.m[n+][]);
}
return ;
}