alan23273850 的刷題筆記
d769: 共有多少種走法?
Tags: fast-exponentiation, graph, matrix
出處：https://zerojudge.tw/ShowProblem?problemid=d769
提交：https://zerojudge.tw/Submissions?problemid=d769&account=allllllan123456
問題：給你一張有 $N\in[1,50]$ 個點的單向無權圖 (編號 1 到 $N$)，其中的每個點 $x$ 都有 $s_{x,y}\in[0,20]$ 條邊可以抵達 $y$，根據這個定義，一條邊可以連接同一個頂點，同時也有多條邊有相同的起訖點。現在固定常數 $k\in[1,10^7]$，接下來有 $Q\le N^2$ 筆詢問，每次問你從點 i 出發剛好走過 $k$ 條邊之後抵達點 j 的方法數有幾種。
解法：這題 AC 率高，應該是因為解法蠻經典的。如果一個矩陣 $M_{k_1}$ 的第 i 列第 j 行表示從 i 出發剛好走過 $k_1$ 條邊之後抵達 j 的方法數，而另一個矩陣 $M_{k_2}$ 的第 i 列第 j 行表示從 i 出發剛好走過 $k_2$ 條邊之後抵達 j 的方法數，那麼矩陣乘法 $M_{k_1+k_2} = M_{k_1}\cdot M_{k_2}$ 的第 i 列第 j 行就表示從 i 出發剛好走過 $k_1 + k_2$ 條邊後抵達 j 的方法數。每次詢問的答案便是 $M_k=(M_1)^{k}$ 的第 i 列第 j 行，這樣就能用快速冪了。
1#include <bits/stdc++.h>
2using namespace std;
3
4struct matrix {
5 int n, e[51][51] = {0};
6 matrix(int size, bool unit=false) : n(size) {
7 if (unit)
8 for (int i=1; i<=n; i++)
9 e[i][i] = 1;
10 }
11 matrix operator*(const matrix& m2) const {
12 matrix ans(n);
13 for (int i=1; i<=n; i++)
14 for (int j=1; j<=n; j++) {
15 for (int k=1; k<=n; k++)
16 ans.e[i][j] += e[i][k] * m2.e[k][j];
17 ans.e[i][j] %= 5281;
18 }
19 return ans;
20 }
21};
22
23int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
24 int N, k;
25 while (cin >> N >> k) {
26 matrix m(N); int x, y, s;
27 while (cin >> x >> y >> s && (x || y || s))
28 m.e[x][y] = s;
29 matrix ans(N, true);
30 while (k) {
31 if (k & 1)
32 ans = ans * m;
33 m = m * m, k >>= 1;
34 }
35 int Q; cin >> Q;
36 while (Q--)
37 cin >> x >> y, cout << ans.e[x][y] << '\n';
38 }
39 return 0;
40}