P4159 [SCOI2009] 迷路
先考虑当路径长度都是1的情况，那么题目要求的其实就是走了\(t\)步到达\(n\)点的方案数
设\(f[i][j][t]\)表示从\(i\)到\(j\)恰好走了\(t\)步的方案数，则
\(f[i][j][t] = \sum\limits_{k=1}^nf[i][k][t-1]*f[k][j][1]\)
而\(f[k][j][1]\)其实就是\(g[i][j]\)即邻接矩阵中两点之间是否有边。
2023-11-04 09:01:16
先考虑当路径长度都是1的情况，那么题目要求的其实就是走了\(t\)步到达\(n\)点的方案数
设\(f[i][j][t]\)表示从\(i\)到\(j\)恰好走了\(t\)步的方案数，则
\(f[i][j][t] = \sum\limits_{k=1}^nf[i][k][t-1]*f[k][j][1]\)
而\(f[k][j][1]\)其实就是\(g[i][j]\)即邻接矩阵中两点之间是否有边。