ZOJ 2853 Evolution 矩陣快速冪與棧溢出避坑

題目模型

給定線性遞推關係，需計算第 n 項。轉移可表示為矩陣乘法，利用**矩陣快速冪**將時間從 O(n) 降為 O(log n)。

關鍵代碼結構

struct Matrix {
    double a[205][205];   // 尺寸由題目決定，通常 ≤ 200
};

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

Matrix mpow(Matrix base, long long exp, int sz) {
    Matrix res; memset(res.a, 0, sizeof(res.a));
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    while (exp) {
        if (exp & 1) res = mul(res, base, sz);
        base = mul(base, base, sz);
        exp >>= 1;
    }
    return res;
}

棧溢出避坑指南

• 現象：Matrix 含大型陣列（如 205×205 double ≈ 336 KB），作為**值傳參**或**局部變量**會佔用大量棧空間，導致 Stack Overflow。
• 解決：
  1. 所有矩陣參數改為 const 引用：const Matrix&。
  2. 函數內部**靜態/全局**分配暫存矩陣，或動態 new。
  3. 或直接將 Matrix 定義為 static / 全局變量。
• 經驗：結構體超過 ~1 MB 即應避免棧上分配；競賽環境棧通常 8~64 MB，但遞歸深度疊加時極易爆棧。

完整可 AC 範例（引用版）

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

const int MAXM = 205;
int MOD, SZ;

struct Matrix {
    double a[MAXM][MAXM];
    Matrix() { memset(a, 0, sizeof(a)); }
};

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

Matrix mpow(Matrix base, long long e) {
    Matrix res;
    for (int i = 0; i < SZ; ++i) res.a[i][i] = 1;
    while (e) {
        if (e & 1) res = mul(res, base);
        base = mul(base, base);
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    while (cin >> n >> MOD) {
        cin >> SZ;
        Matrix T;
        for (int i = 0; i < SZ; ++i)
            for (int j = 0; j < SZ; ++j)
                cin >> T.a[i][j];
        Matrix ans = mpow(T, n);
        cout << (long long)ans.a[0][0] % MOD << "\n";
    }
    return 0;
}