［原創題］危機百科 - 提示、題解

題目簡介

給定一個網站，每個網頁有多個網址，會導向這個網站的某個網頁。給定操作次數及目標，求在指定操作次數後，從首頁出發能到達目標網頁的路徑數量。

提示

推薦打開之後想想看再繼續，不要一次使用全部

提示1

具體來說，要怎麼紀錄網站中網頁和網頁的關聯性？

提示2

好像能夠應用高二數學中的知識…？

題解

這東西莫名其妙的長，花了我好多時間。如果你不用這個就解開了，那也推薦你看看我的做法，並跟我分享你的做法。

點開會有完整解答，請想過後再開喔

思路

這題讓我翻譯成白話文：給定一個有向圖，求從0走n步後到t的路徑數量。這題如果單純到處走的話很容易TLE（路徑數量過於龐大），於是我們需要換個方法：使用矩陣快速幂

先別滑走 我一步一步解釋給你聽 這東西其實超級萬用

在了解怎麼實作時，我們需要搞清楚幾件事

(1) 怎麼紀錄這張圖

一般來說，對於包含n個點的有向圖都會建立一個n*n的表格，定義m[i][j]為從j走到i的權重。如果像這題沒有權重，可以儲存是否連通(1/0)

為什麼不是i走到j的？等等矩陣乘法會告訴你。但是對於一般的圖論題目或是熟悉這個邏輯的人，並不強制要求這樣安排。

以下包括許多Latex語句，使用閱讀器等工具閱讀可能造成閱讀障礙。如果等等沒有看到可怕的矩陣請考慮更換瀏覽器。

(2) 這張表能幹嘛？

在回答這題之前我們需要了解「矩陣乘法」以及「轉移矩陣」，如果不了解的話我會簡單介紹一下。

---

關於矩陣乘法（沒學過或想複習都可以看）

矩陣是類似二維陣列的數學結構，包含列（row，橫的一排叫做列）以及行（column，直的一排叫做行）。例如以下是包含$m$列$n$行的矩陣$A$

\[A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{bmatrix}\]

而矩陣乘法中，如果$A$行數=$B$列數=$n$

\[AB_{ij} = \sum_{r=1}^{n} A_{ir} \times B_{rj}\]

這句話翻譯成白話文是：乘積矩陣$AB$的第$i$列第$j$行的值等於矩陣$A$的第$i$列由左而右與矩陣$B$的第$j$行由上而下一個一個找出來相乘後的總和。例如

\[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{bmatrix} \times \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \\ \end{bmatrix} = \begin{bmatrix} 58 & 64 \\ 139 & 154 \\ \end{bmatrix}\]

其中$58 = 1 \times 7 + 2 \times 9 + 3 \times 11$，其他類推。請注意：矩陣乘法不是交換律，也就是說$AB \neq BA$。

---

關於轉移矩陣（一樣是沒學過或是想複習的）

舉個簡單的例子，如果有矩陣 \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix}\) ，你會發現任何矩陣 \(B = \begin{bmatrix} x \\ y \\ \end{bmatrix}\) 進行$A \times B$運算後都會得到$x$和$y$交換的結果 \(\begin{bmatrix} y \\ x \\ \end{bmatrix}\) ，稱A為一種轉移矩陣（這裡為將座標轉換成對於$y=x$的對稱點）。通常$B$僅包含一行資料，會得到一行資料；多筆資料可以合併（擺到第二、三…行）。例如 \(\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix}\) 即為兩筆資料$(1, 0)$和$(0, 1)$的轉移結果。

---

有了這兩個先備知識，你會發現其實剛剛(1)中存起來的圖是一種轉移矩陣。我們將範例一、二的矩陣畫出來（注意這裡定義$M_{ij}$為是否能從$j$走到$i$，以方便矩陣乘法計算）：

• 範例一 \(M = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ \end{bmatrix}\) 若從0出發則計算 \(\begin{bmatrix} 1 & 0 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}\) 代表走一步後能到達0和1。
• 範例二 \(M = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{bmatrix}\) 若從0出發則計算 \(\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ \end{bmatrix}\) 代表走一步後只能到達2。

恭喜我們完成走一步的判斷了，可以試試看做出第三個範例測資的矩陣後，我們再繼續看下去。

你可能發現了，學完這個之後你會精通for迴圈

運算過程中，你會發現這是「1, 0」在跟每一個點的數值做計算後得出一個「結論」，代表走完這步之後會到的所有地方。可以發現範例三的矩陣是 \(\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}\) ，如果以這個方式走兩步，你會發現數字不僅僅限於0和1： \(\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix}\)

請先嘗試由右而左結合，你可能會算的比較輕鬆

請你回推一下矩陣每格中的意義，以及參與矩陣乘法的各個元素，你會發現：矩陣乘法正在幫助你嘗試每一種可能，對於每個可能來訪的點用0/1乘法判斷來訪路徑數相加，而運算結果即最後能夠停留在這個點上的路徑數量。我們可以得到一個結論，假設轉移矩陣為A：

\[A^n \begin{bmatrix} 1 \\ 0 \\ \cdots \\ 0 \end{bmatrix} = \begin{bmatrix} \text{從0出發，走n步，到0的路徑數} \\ \text{從0出發，走n步，到1的路徑數} \\ \cdots \\ \text{從0出發，走n步，到k的路徑數} \\ \end{bmatrix}\]

能發現我們所求的答案為

\[[A^n \begin{bmatrix} 1 \\ 0 \\ \cdots \\ 0 \end{bmatrix} ]_{t1}\]

你應該已經可以設計程式，產生正確的結果了。對於沒有學過函式的人，可以先了解看看函式的製作方式，應該可以讓程式更加清楚。

(3) 似乎還沒縮減運算成本，反而增加了？

若要減少運算量，則需要了解：矩陣乘法具有結合律，即矩陣$A(AB)=(AA)B$，所以我們可以先計算出$A^n$後再和$B$矩陣相乘。而讓程式加速，就要使用一直還沒拿出來的「快速幂」了！

首先我們要了解「二進制」（以$(n)_2$表示$n$為一個二進位的數）：逢二進位，所以由右而左的第$n$位不是$10^{n-1}$，而是$2^{n-1}$，所以$5 = (101)_2$。這時候，我們可以根據指數律$a^{m+n}=a^m \times a^n$且$(A^n)^m = A^{nm} \rightarrow (A^n)^2 = A^{2n}$，所以從$A^1$開始，每次平方，透過二進制判斷是否需要乘進去，就會把時間從$O(n)$變成$O(\log{n})$。以$A^5$為例，可以得到

\[A^{5} = A^{(101)_2} = A^{(100)_2 + (1)_2} = A^{(100)_2} \times A^{(1)_2} = A^4 \times A^1 = (A^2)^2 \times A\]

程式上，可以用%2運算取得最後一位的值，並用/2（或進階可以用>>1）把最右邊一位刪除。

(4) 等等，我還是WA

因為我們沒有處理取模的部分！但是我們要怎麼取模？

在進行矩陣乘法時，由於路徑數量可能會快速增長，直接相乘的結果很容易超過變數的儲存範圍（例如int約能存$2 \times 10^9$）造成溢位。因此我們需要在計算過程中適當地進行取模運算。

根據模運算的性質，我們知道$(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$。這代表我們可以在每次乘法運算後立即取模，而不影響最終結果的正確性。

在矩陣乘法中，計算$(C_{ij} = \sum_{k=1}^{n} A_{ik} \times B_{kj}$時，我們需要注意以下幾點：

• 在每次乘法後取模（Python以外）：計算$(A_{ik} \times B_{kj})$後立即對$(10^9+7)$取模，防止加起來的時候爆炸
• 在累加後也要取模（全部）：將結果加到$(C_{ij})$後可以取模
• 型別轉換（Python以外）：在相乘前乘以1LL強制換成long long，確保乘法過程中不會溢位

這樣就能確保整個矩陣快速冪的計算過程都在安全的數值範圍內進行，避免溢位導致的錯誤答案。

完整程式碼

請注意，本程式碼僅供寫法上參考，直接複製貼上程式碼會導致你學不到任何東西。

程式碼中我因個人習慣將$M_{ij}$存為mp[j][i]，故處理及輸出時會與上面部分敘述相反。提供額外一種做法給你。

C++ 範例程式碼

#include <bits/stdc++.h>
using namespace std;
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define M 1000000007

vector<vector<int>> f(vector<vector<int>>& mp1, vector<vector<int>>& mp2) {
    vector<vector<int>> res = vector<vector<int>>(mp1.size(), vector<int>(mp2[0].size(), 0));
    for (int i = 0; i < mp1.size(); i++) {
        for (int j = 0; j < mp2[0].size(); j++) { 
            for (int k = 0; k < mp1.size(); k++) {
                res[i][j] += ((1LL*mp1[i][k] * mp2[k][j])%M);
                res[i][j] %= M;
            }
        }
    }
    return res;
}

int main() {
    raymondwengcode;

    int m, n, k;
    cin >> n >> m >> k;
    vector<vector<int>> mp = vector<vector<int>>(m, vector<int>(m, 0));
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        mp[a][b] = 1;
    }
    vector<vector<int>> res = vector<vector<int>>(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++) {
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n%2) {
            res = f(res, mp);
        }
        n >>= 1;
        mp = f(mp, mp);
    }
    int t;
    cin >> t;
    cout << res[0][t]%M;

    return 0;
}

Python 範例程式碼

M = 10**9 + 7
def f(a, b, m):
    res = [[0 for _ in range(m)] for _ in range(m)]
    for i in range(m):
        for j in range(m):
            for k in range(m):
                res[i][j] += a[i][k] * b[k][j]
                res[i][j] %= M
    return res

n, m, k = map(int, input().split())
mp = [[0 for _ in range(m)] for _ in range(m)]
res = [[0 for _ in range(m)] for _ in range(m)]
for _ in range(k):
    x, y = map(int, input().split())
    mp[x][y] = 1
for i in range(m):
    res[i][i] = 1
while n>0:
    if n%2 == 1:
        res = f(res, mp, m)
    mp = f(mp, mp, m)
    n //= 2
t = int(input())
print(res[0][t])