很容易想到记忆化搜索的算法。 令dp[n][T]为到达n点时时间为T的路径条数。则dp[n][T]=sigma(dp[i][T-G[i][n]]); 但是空间复杂度为O(n*T),时间复杂度O(n*n*T).
虽然本题的n<=10,但T最大可到1e9。行不通。
如果题目中的边的权值非0即1的话，显然1-n的长度为T的路径中数为 该图的邻接矩阵的T次幂。
实际上题目中的边权值<10. 可以用拆点的方法转化为边权值非0即1的情况。
即 将图中的每个点拆成至多9个点，首先将每个点的第i个点和第i+1个点连一条权值为1的边。另外，如果原图中Eij=m，则将新图的第i个点拆成的第m点和j点的第一个点连一条权值
为1的边。这样就完全转化为我们可以解决的问题形式了。矩阵快速幂可以在O(n'^3*logT)的时间内完成。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi 3.1415926535 # define eps 1e-9 # define MOD 100000007 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=2505; //Code begin... struct Matrix{int matrix[95][95];}a, sa, unit; int n, T; char G[11][11]; Matrix Mul(Matrix a,Matrix b) //矩阵乘法(%m) { Matrix c; for (int i=0; i<9*n; ++i) for (int j=0; j<9*n; ++j) { c.matrix[i][j]=0; for (int l=0; l<9*n; ++l) c.matrix[i][j]+=a.matrix[i][l]*b.matrix[l][j]; c.matrix[i][j]%=2009; } return c; } Matrix Cal(int exp) //矩阵快速幂 { Matrix p=a, q=unit; if (exp==0) return p; while (exp!=1) { if (exp&1) exp--, q=Mul(p,q); else exp>>=1, p=Mul(p,p); } return Mul(p,q); } int main () { scanf("%d%d",&n,&T); FO(i,0,n) scanf("%s",G[i]); FO(i,0,n) FOR(j,0,7) a.matrix[i*9+j][i*9+j+1]=1; FO(i,0,n) FO(j,0,n) { if (G[i][j]=='0') continue; a.matrix[i*9+G[i][j]-'1'][j*9]=1; } unit=a; sa=Cal(T-1); printf("%d ",sa.matrix[0][9*(n-1)]); return 0; }