因为边权最大为9，记录前9个状态矩阵快速幂。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 15 #define maxn 150 #define mod 2009 #define inf 100 using namespace std; struct matrix { int a[maxn][maxn]; }a,b; int n,t,map[maxv][maxv],x,y,dp[maxv][10]; char s[maxv]; void pre_dp() { dp[1][0]=1; for (int i=1;i<=9;i++) { for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) if (map[k][j]<=i) dp[j][i]=(dp[j][i]+dp[k][i-map[k][j]])%mod; } } void get_table() { int cnt=0; for (int i=1;i<=9;i++) for (int j=1;j<=n;j++) a.a[1][++cnt]=dp[j][i]; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (map[i][j]!=inf) b.a[(9-map[i][j])*n+i][8*n+j]=1; int p1=n+1,p2=1; while (p1<=9*n) { b.a[p1][p2]=1; p1++;p2++; } } matrix mul(matrix a,matrix b) { matrix c; for (int i=1;i<=9*n;i++) for (int j=1;j<=9*n;j++) c.a[i][j]=0; for (int i=1;i<=9*n;i++) for (int j=1;j<=9*n;j++) for (int k=1;k<=9*n;k++) c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod; return c; } void f_pow(int y) { while (y) { if (y&1) a=mul(a,b); b=mul(b,b); y>>=1; } } int main() { scanf("%d%d",&n,&t); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=n;j++) { map[i][j]=s[j-1]-'0'; if (!map[i][j]) map[i][j]=inf; } } pre_dp(); if (t<=9) {printf("%d ",dp[n][t]%mod);return 0;} get_table(); f_pow(t-9); printf("%d ",a.a[1][9*n]%mod); return 0; }