HDU 5411 CRB and Puzzle：矩陣快速冪計算路徑數

題目大意

• 有向圖 n ≤ 50 點，鄰接矩陣 A。
• 求長度 ≤ m-1 的路徑總數（模 2015），即 sum_{k=0}^{m-1} (A^k) 全元素和。

矩陣增廣技巧

構造 (n+1) × (n+1) 矩陣 M：

M = [ A  0 ]
    [ 1  1 ]   (最後一行全 1，最後一列除右下角外為 0)

則 M^m 的右下角 (n,n) 元素即為 I + A + A² + ... + A^{m-1} 的所有元素和。

優化：縮小矩陣維度

只需一行累加器，構造 (n+1) × (n+1)：

• 前 n 行前 n 列 = A。
• 第 n 行前 n 列 = 全 1（累加器）。
• 第 n 行第 n 列 = 1。
• 其餘 0。

初始向量 V = [0...0, 1]^T，計算 M^m * V，答案在最後一行。矩陣乘法模 2015 可移到第二層循環避免溢出並加速。

完整代碼（縮小版）

#include 
using namespace std;
const int MOD = 2015;
struct Matrix {
    int n;
    vector> a;
    Matrix(int n_, bool ident=false) : n(n_), a(n_, vector(n_)) {
        if (ident) for (int i=0;i= 1<<30) r.a[i][j] %= MOD; // 批量取模
                }
        for (int i=0;i>= 1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; long long m; cin >> n >> m;
        Matrix M(n+1);
        for (int i=0;i> k;
            while (k--) { int v; cin >> v; M.a[i][v-1] = 1; }
        }
        M.a[n][n] = 1;
        M = mpow(M, m);
        int ans = 0;
        for (int j=0;j<=n;++j) ans = (ans + M.a[n][j]) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 矩陣乘法 O(n³)，n ≤ 51。
• 快速冪 O(n³ log m)，m ≤ 1e9 約 30 步。
• 單測試用例 ~51³ × 30 ≈ 4M 運算，20 組約 80M，C++ 0.1s 級。