[SCOI2009] 迷路
题意
给出一张带权有向图，从 \(1\) 号点出发，必须在恰好 \(t\) 时刻到达 \(n\)。
中途不能停留，求有多少种方案。
思路
先考虑边权为 \(1\) 的情况，设 \(f_{t,i,j}\) 为从 \(i\) 走到 \(j\) 花费 \(t\) 个时刻的方案数。
\(f_{t,i,j}=\sum{f_{t-1,i,k} \times f_{t-1,k,j}}\)，注意到这就是矩阵乘法的形式，又注意到 \(f_1\) 就是邻接矩阵。
所以 \(f_1^t\) 就是最终矩阵，答案即 \(f_{1,1,n}^{t}\)。
再考虑边权不为 \(1\) 的情况，如何把边权为 \(w\) 的边转化为边权为 \(1\) 的边。
考虑把一个点 \(i\) 拆成 \(10\) 个点 \((i,0),(i,1),\dots,(i,9)\)。
将 \((i,j)\) 向 \((i,j-1)\) 连一条边权为 \(1\) 的边。
如果点 \(i\) 与点 \(j\) 之间有一条边权为 \(w\) 的边，将 \((i,0)\) 向 \((j,w-1)\) 连一条边权为 \(1\) 的边。
因为只有 \((i,0)\) 有出边，\((i,k)\) 想要出去必须先花费 \(k\) 的时间走到 \((i,0)\)。
这样保证了 \((i,0)\) 到 \((j,0)\) 必定花费 \(1+(w-1)=w\) 的时间，与原图等价。
这样我们就把原图转化为了边权为 \(1\) 的图，用邻接矩阵快速幂就能求出答案。
时间复杂度：\(O(n^3)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 2009;
int n, t, cnt, f[N][N], id[N][N];
char str[N];
struct Matrix {
int h, l, a[N][N];
void init(int H, int L, bool f) {
h = H, l = L;
for (int i = 1; i <= h; i ++)
for (int j = 1; j <= l; j ++) {
if (!f) a[i][j] = 0;
else if (i == j) a[i][j] = 1;
}
}
Matrix operator * (const Matrix& b)const{
Matrix ret;
ret.init(h, b.l, 0);
for (int i = 1; i <= h; i ++)
for (int j = 1; j <= b.l; j ++)
for (int k = 1; k <= l; k ++)
ret.a[i][j] += a[i][k] * b.a[k][j],
ret.a[i][j] %= M;
return ret;
}
void input() {
for (int i = 1; i <= h; i ++)
for (int j = 1; j <= l; j ++)
cin >> a[i][j];
}
void output() {
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= l; j ++)
cout << a[i][j] << ' ';
cout << '\n';
}
}
} A, B;
Matrix qpow(Matrix a, int p) {
Matrix ret;
ret.init(a.h, a.l, 1);
for (; p; p >>= 1, a = a * a)
if (p & 1) ret = ret * a;
return ret;
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= 9; j ++) {
id[i][j] = ++ cnt;
}
}
for (int i = 1; i <= n; i ++) {
scanf("%s", str + 1);
for (int j = 1; j <= n; j ++) {
if (str[j] == '0') continue;
int w = str[j] - '0';
f[id[i][0]][id[j][w - 1]] = 1;
}
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= 9; j ++)
f[id[i][j]][id[i][j - 1]] = 1;
A.h = A.l = cnt;
for (int i = 1; i <= cnt; i ++)
for (int j = 1; j <= cnt; j ++)
A.a[i][j] = f[i][j];
A = qpow(A, t);
printf("%d\n", A.a[id[1][0]][id[n][0]]);
return 0;
}