1 1 1 2 2 0 0 3 7 23 47 16
234 2799 72937Hint
题解及代码：
矩阵快速幂的题目，推出矩阵就可以了，具体推的方法就是有矩阵的第一列推出第二列，以此类推就可以了。
这里给出10的矩阵：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const __int64 mod=10000007;
struct mat //矩阵的定义
{
__int64 t[13][13];
void set()
{
memset(t,0,sizeof(t));
}
} a,b,c;
mat multiple(mat a,mat b,int n,int p) //矩阵相乘函数
{
int i,j,k;
mat temp;
temp.set();
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
if(a.t[i][j]!=0)
for(k=0; k<n; k++)
temp.t[i][k]=(temp.t[i][k]+a.t[i][j]*b.t[j][k]+p)%p;
}
return temp;
}
mat quick_mod(mat b,int n,int m,int p)
{
mat t;
t.set();
for(int i=0;i<n;i++) t.t[i][i]=1;
while(m)
{
if(m&1)
{
t=multiple(t,b,n,p);
}
m>>=1;
b=multiple(b,b,n,p);
}
return t;
}
void init(int n)
{
a.set();
for(int i=0;i<=n;i++)
{
if(i==0)
for(int j=0;j<=n;j++)
a.t[j][i]=1;
else if(i==1)
for(int j=1;j<=n;j++)
a.t[j][1]=10;
else
for(int j=i;j<=n;j++)
a.t[j][i]=1;
}
}
int main()
{
int n,m;
__int64 s[14];
while(scanf("%d%d",&n,&m)!=EOF)
{
s[0]=3;
s[1]=23;
for(int i=2;i<=n+1;i++)
{
scanf("%I64d",&s[i]);
}
init(n+1);
b=quick_mod(a,n+2,m,mod);
__int64 ans=0;
for(int i=0;i<=n+1;i++)
ans=(ans+(s[i]*b.t[n+1][i])%mod)%mod;
printf("%I64d\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/knight_kaka/article/details/39296743