ZOJ 3497 Mistwald：矩陣快速冪判斷 P 步可達性

題目模型

n×m 矩陣，每格有 4 個傳送門指向相鄰格。起點 (1,1)，終點 (n,m)。到達終點即停止（無出邊）。問恰走 P 步（0 ≤ P ≤ 1e8）能否到達終點。輸出 True（只能在終點）、Maybe（終點與其他點均可達）、False（無法達終點）。

矩陣快速冪 + 狀態壓縮

• 將格子編號 1..N (N=n*m)。
• 建立鄰接矩陣 A：A[i][j]=1 表示可從 i 一步到 j。終點無出邊。
• 計算 A^P，若 (A^P)[1][N] = 1 則可達。
• 但需區分 True/Maybe：需知道 P 步後除終點外是否還能在其他點。

優化：分解最後一步

預處理：

• can[i]=1：從 i 一步可達終點。
• yes[i]=1：從 i 一步可達非終點。

計算 B = A^(P-1)。若 P=0 特判。對於起點 1，檢查 B[1][i]：

• 存在 i 使 B[1][i] && can[i] → 可達終點。
• 同時存在 i 使 B[1][i] && yes[i] → 也可達其他點 → Maybe。
• 僅前者 → True；均無 → False。

布爾矩陣乘法

用位運算加速：C[i][j] = OR_k (A[i][k] AND B[k][j])。N ≤ 900，O(N^3 log P) 可通過（或用 bitset 優化至 O(N^3/64 log P)）。

完整 C++ 核心邏輯

struct Matrix { bool a[31][31]; }; // 假設 n,m ≤ 30? 實際 N=n*m
Matrix mul(Matrix A, Matrix B) {
    Matrix C;
    for i,j,k: C[i][j] |= A[i][k] & B[k][j];
    return C;
}
Matrix pow(Matrix A, long long p) {
    Matrix R; for i: R[i][i]=1;
    while(p){ if(p&1) R=mul(R,A); A=mul(A,A); p>>=1; }
    return R;
}

（完整代碼較長，核心為上述邏輯）