題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 AT_dp_r Walk

Problem Statement

題目簡述

給定一個 $N$ 個頂點的有向圖（以鄰接矩陣 $A$ 給出， $a_{i,j}=1$ 代表有邊， $0$ 代表無邊），求圖中長度恰好為 $K$ 的有向路徑總數。答案對 $10^9+7$ 取模。

Constraints

約束條件

$1 \le N \le 50$
$1 \le K \le 10^{18}$
$a_{i,j} \in \{0, 1\}$ ，且 $a_{i,i} = 0$ （無自環）

思路：矩陣快速冪

狀態定義與轉移

設 $f[k][i][j]$ 為從頂點 $i$ 走恰好 $k$ 步到達頂點 $j$ 的路徑數。

根據「最後一步」的思想，列出轉移方程：

f[k][i][j] = \sum_{m=1}^{N} f[k-1][i][m] \times a_{m,j}

直觀理解

要從 $i$ 走 $k$ 步到 $j$ ，可以先走 $k-1$ 步到任意中繼點 $m$ ，再從 $m$ 經一條邊到 $j$ 。

邊界條件： $f[0][i][j] = [i = j]$ （走 0 步只能停在原地）。

矩陣乘法的本質

觀察轉移方程，它與矩陣乘法的定義完全一致：

(C)_{ij} = \sum_{m} (A)_{im} \times (B)_{mj}

若將 $f[k]$ 視為矩陣 $F_k$ ，鄰接矩陣為 $A$ ，則： $F_k = F_{k-1} \times A$ 。

由於 $F_0 = I$ （單位矩陣），歸納可得：

F_k = A^k

結論

$(A^K)_{i,j}$ 即為從 $i$ 到 $j$ 長度恰為 $K$ 的路徑數。

快速冪加速

$K$ 可達 $10^{18}$ ，逐次相乘不可行。使用快速冪技巧，將乘法次數降至 $O(\log K)$ 。

最終答案為 $A^K$ 中所有元素之和：

\text{Answer} = \sum_{i,j} (A^K)_{i,j} \pmod{10^9+7}

複雜度分析

時間複雜度： $\mathcal{O}(N^3 \log K)$
空間複雜度： $\mathcal{O}(N^2)$

Code

MOD = int(1e9 + 7)

class Matrix:
    def __init__(self, mat):
        self.mat = mat

    def __mul__(self, other):
        assert len(self.mat[0]) == len(other.mat)
        return Matrix([[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*other.mat)]
                for row in self.mat])
    
    def __pow__(self, k):
        assert len(self.mat) == len(self.mat[0])
        n = len(self.mat)
        res = Matrix([[int(i == j) for j in range(n)] for i in range(n)])
        base = self
        while k > 0:
            if k & 1:
                res *= base
            base *= base
            k >>= 1
        return res
    
    def __getitem__(self, i):
        return self.mat[i]

def solve():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    A = Matrix(A)
    Ak = A ** K
    print(sum(sum(row, ) for row in Ak.mat))
    ans = 0
    for i in range(N):
        for j in range(N):
            ans = (ans + Ak[i][j]) % MOD
    print(ans)

if __name__ == '__main__':
    solve()