给定一个n个点的有向图，给定邻接矩阵，每条边的距离都是1-9，求从1号点走到n号点且距离恰好为T的方案数量%2009. n<=10,T<=10^9
题解：看到T的范围很容易想到矩阵乘法，但是距离不全是1没法搞，所以我们可以把每条边拆点，这样就保证了边权都是1，可以矩阵乘法啦
但是这样的话点的数量有点多，最多n^2*9 ，也就是900个，直接搞还是T。
但是我们发现我们没必要把每条边拿出来拆，只要对每个点拆出9个点，表示离这个点距离为0-8的点，就可以啦，这样点的数量V=n*9
复杂度V^3*logT
#include<iostream> #include<cstdio> #include<cstring> #define mod 2009 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,T; int f[15][15][35]; char st[15]; int id[15][15],tot=0; struct sq{ int f[95][95]; int n,m; sq operator *(sq y) { sq c;memset(c.f,0,sizeof(c.f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=y.m;k++) c.f[i][j]=(c.f[i][j]+f[i][k]*y.f[k][j])%mod; c.n=n;c.m=y.m; return c; } }s,s2; int main() { n=read();T=read(); for(int i=1;i<=n;i++) for(int j=0;j<=8;j++) { id[i][j]=++tot; if(j)s.f[tot][tot-1]=1; } s.n=s.m=tot; for(int i=1;i<=n;i++) { scanf("%s",st+1); for(int j=1;j<=n;j++) if(st[j]!='0') s.f[id[i][0]][id[j][st[j]-'1']]=1; } s2.n=1;s2.m=tot; s2.f[1][id[1][0]]=1; for(;T;T>>=1,s=s*s) if(T&1) s2=s2*s; cout<<s2.f[1][id[n][0]]; return 0; }