POJ 3150 Cellular Automaton：循環矩陣快速冪優化至 O(n² log k)

題目大意

n 個細胞排成環，初始狀態 a[i]。每步轉移：第 i 細胞新值 = 所有滿足 min(|i-j|, n-|i-j|) ≤ d 的 j 細胞舊值之和模 m。求 k 步後狀態。n ≤ 500, k ≤ 10^9。

矩陣模型

轉移矩陣 B：B[i][j] = 1 若 min(|i-j|, n-|i-j|) ≤ d，否則 0。則一步轉移 a' = a × B (mod m)，k 步 a × B^k。

關鍵觀察：循環矩陣

B 每行是上一行**右循環移位 1 位**得到。因此 B 由第一行完全決定，矩陣乘法可優化：

• 只計算結果矩陣第一行。
• 其餘行由第一行循環移位得出。

將矩陣乘法從 O(n³) 降為 O(n²)。

快速冂算法

using ll = long long;
vector multiply(const vector& a, const vector& b, int n, int mod) {
    vector c(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i] = (c[i] + a[j] * b[(i - j + n) % n]) % mod; // 循環卷積
    return c;
}

vector power(vector base, long long exp, int n, int mod) {
    vector res(n); res[0] = 1; // 單位矩陣第一行
    while (exp) {
        if (exp & 1) res = multiply(res, base, n, mod);
        base = multiply(base, base, n, mod);
        exp >>= 1;
    }
    return res;
}

完整流程

1. 讀入 n, m, d, k 及初始向量 a。
2. 構造基矩陣第一行 base：base[i] = (min(i, n-i) <= d) ? 1 : 0。
3. 計算 trans = power(base, k, n, m)（即 B^k 第一行）。
4. 最終狀態 ans[i] = Σ a[j] * trans[(i-j+n)%n] % m（循環卷積）。

C++ 實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector conv(const vector& a, const vector& b, int n, int mod) {
    vector c(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i] = (c[i] + a[j] * b[(i - j + n) % n]) % mod;
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, d; long long k;
    while (cin >> n >> m >> d >> k) {
        vector a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector base(n);
        for (int i = 0; i < n; i++)
            base[i] = (min(i, n - i) <= d) ? 1 : 0;
        vector trans(n); trans[0] = 1; // 單位
        while (k) {
            if (k & 1) trans = conv(trans, base, n, m);
            base = conv(base, base, n, m);
            k >>= 1;
        }
        vector ans = conv(a, trans, n, m);
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

複雜度

n=500, log k≈30 → ~7.5×10⁶ 次乘加，極快。

總結

POJ 3150 展示了循環矩陣結構如何將矩陣快速冂從 O(n³ log k) 優化至 O(n² log k)。核心洞見：循環矩陣由第一行決定，乘法等價於循環卷積。此技巧適用於所有「環狀結構、平移不變」的線性遞推問題。