传送门
矩阵快速幂优化dp简单题。
考虑状态转移方程：
f[time][u]=∑f[time−1][v]f[time][u]=\sum f[time-1][v]f[time][u]=∑f[time−1][v]
把一个点拆成9个来转换边长，然后根据题意模拟连边就行了。
最后用矩阵快速幂优化一下转移就能过啦。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,t,m;
char s[50];
const int mod=2009;
struct Matrix{
int val[100][100];
Matrix(int x=0){
memset(val,0,sizeof(val));
for(int i=0;i<m;++i)val[i][i]=x;
}
inline Matrix operator*(const Matrix&b){
Matrix ret(0);
for(int i=0;i<m;++i)for(int k=0;k<m;++k)for(int j=0;j<m;++j)(ret.val[i][j]+=val[i][k]*b.val[k][j]%mod)%=mod;
return ret;
}
friend inline Matrix operator^(Matrix a,int p){Matrix ret(1);for(;p;p>>=1,a=a*a)if(p&1)ret=ret*a;return ret;}
};
#define idx(x,y) ((x)*9+(y))
int main(){
scanf("%d%d",&n,&t),m=n*9;
Matrix ans(0),a(0);
ans.val[0][0]=1;
for(int i=0;i<n;++i){
scanf("%s",s);
for(int j=0;j<n;++j){
int c=s[j]-'0';
if(!c)continue;
++a.val[idx(i,c-1)][idx(j,0)];
}
}
for(int i=0;i<n;++i)for(int j=0;j<8;++j)++a.val[idx(i,j)][idx(i,j+1)];
ans=ans*(a^t);
printf("%d",ans.val[0][idx(n-1,0)]);
return 0;
}