TIOJ-1428

發表於 更新於 Disqus：

給一張$n$個點與$m$條邊的有向圖，再給一個數字$L$。

$Q$筆詢問，每筆詢問從$a$走到$b$且恰好經過$L$條邊(可重複)的路徑有幾條

$n\le 150, m\le 10^6, Q\le 20000, L\le 10^9$

首先我們定義dp狀態，dp[L][a][b]為從$a$到$b$且恰好經過$L$條邊的路徑數量。

而我們有以下轉移式:
$$dp[M+N][a][b] = \sum_{k=0}^{n-1}dp[M][a][k]\times dp[N][k][b]$$
可以理解成考慮剛好走到$M$步的每個中繼點，接下來一定得花$N$步走到終點。

如果用矩陣的方式表示dp，令$dp[M]=A^M$，則:
$$A^{M+N}[a][b] = \sum_{k=0}^{n-1}A^M[a][k]\times A^N[k][b]$$
你會發現他剛好就是矩陣乘法的定義! 所以我們可以再寫成這樣:
$$A^{M+N}=A^M\times A^N$$
至於$A^1$呢? 不難發現他剛好就是這張圖的鄰接矩陣(每條邊代表著一條剛好經過一條邊的路徑)。

所以把輸入轉成鄰接矩陣之後，我們就能使用矩陣快速冪來快速計算出$A^L$，然後就能$\mathcal{O}(1)$回答每筆詢問了。

複雜度$\mathcal{O}(n^3\log L+Q)$。

使用struct可以讓code變整齊>< 然後這題我WA超久才發現他的mod是$10^9+9$而不是$10^9+7$…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*--------------------------------------------------------------------------------------*/

const int MOD = 1e9 + 9;
int n;

struct mat {
	int arr[150][150];
	mat() {
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				arr[i][j] = 0;
	}
	mat operator*(mat &b) {
		mat c;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				for(int k = 0; k < n; k++)
					c.arr[i][j] = (c.arr[i][j] + 1LL * arr[i][k] * b.arr[k][j]) % MOD;
		return c;
	}
};

signed main() { EmiliaMyWife
	int m, q, l;
	cin >> n >> m >> q >> l;
	
	mat res, owo;
	for(int i = 0; i < n; i++)
		res.arr[i][i] = 1;
	//初始化為單位矩陣
	
	for(int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		owo.arr[a][b]++;
	}
	//鄰接矩陣
	
	for(; l; owo = owo * owo, l >>= 1)
		if(l & 1)
			res = res * owo;
	//矩陣快速冪

	while(q--) {
		int a, b;
		cin >> a >> b;
		cout << res.arr[a][b] << '\n';
	}
}