POJ 3735 Training little cats：矩陣快速冪解決貓咪花生循環操作

題目大意

有 n 隻貓，初始花生數皆為 0。給定 k 個操作組成一組，循環執行 m 次。操作三種：

1. g i：第 i 隻貓 +1 顆花生
2. e i：第 i 隻貓花生歸零
3. s i j：第 i、j 隻貓交換花生數

求最終每隻貓花生數。n ≤ 100, m ≤ 10^9, k ≤ 100。

核心洞察：線性變換 = 矩陣乘法

設狀態向量 V = [總和, 猫1, 猫2, ..., 猫n]^T（維度 n+1），第一維固定為 1 用於處理「加常數」操作。每個操作對應一個 (n+1)×(n+1) 變換矩陣 M，使 V' = M × V。一組操作的綜合矩陣 A = M_k ... M_1。循環 m 次即 A^m。最終答案為 (A^m × V0)[1..n]。

矩陣構造規則（初始為單位矩陣）

完整 AC 代碼（C++，含矩陣快速冪）

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 105;

struct Matrix {
    int64 a[MAXN][MAXN];
    void identity(int n) { memset(a, 0, sizeof(a)); for (int i=0;i<=n;++i) a[i][i]=1; }
};

Matrix mul(const Matrix& A, const Matrix& B, int n) {
    Matrix C; memset(C.a, 0, sizeof(C.a));
    for (int i=0;i<=n;++i)
        for (int k=0;k<=n;++k) if (A.a[i][k])
            for (int j=0;j<=n;++j)
                C.a[i][j] += A.a[i][k] * B.a[k][j];
    return C;
}

Matrix mpow(Matrix base, long long exp, int n) {
    Matrix res; res.identity(n);
    while (exp) {
        if (exp & 1) res = mul(res, base, n);
        base = mul(base, base, n);
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; long long m;
    while (cin >> n >> m >> k) {
        if (n==0 && m==0 && k==0) break;
        Matrix A; A.identity(n);
        for (int i=0;i> op;
            if (op == 'g') {
                int idx; cin >> idx; A.a[0][idx] += 1;
            } else if (op == 'e') {
                int idx; cin >> idx;
                for (int r=0;r<=n;++r) A.a[r][idx] = 0;
            } else { // 's'
                int i, j; cin >> i >> j;
                for (int r=0;r<=n;++r) swap(A.a[r][i], A.a[r][j]);
            }
        }
        if (m == 0) { for (int i=1;i<=n;++i) cout << 0 << (i==n?'\n':' '); continue; }
        Matrix R = mpow(A, m, n);
        for (int i=1;i<=n;++i) cout << R.a[0][i] << (i==n?'\n':' ');
    }
    return 0;
}

關鍵點總結

1. 狀態增維：引入常數 1 維度，將「加常數」操作線性化
2. 列操作視角：右乘矩陣對應列變換，構造直觀
3. 快速冪：O((n+1)³ log m) ≈ 10⁶ 操作，極快
4. 長整型：花生數可能巨大，用 long long（POJ 需 %lld 或 %I64d）

複雜度分析

• 時間：O((n+1)³ log m) ≈ 101³ × 30 ≈ 3×10⁷
• 空間：O((n+1)²) ≈ 10⁴