HPUOJ 1295 核反應堆：矩陣快速冪與遞推關係求解

HPUOJ 1295「核反應堆」描述質點碰撞繁殖過程：高能質點產生 3 高能 + 1 低能，低能質點產生 2 高能 + 1 低能。初始 1 高能，每微秒所有質點同時碰撞。求 n 微秒後高能/低能質點數。本文推導遞推關係並給出 O(log n) 矩陣快速冪解法（雖 n≤33 可直接遞推）。

遞推關係建模

設 H[n]、L[n] 為 n 微秒後高能、低能質點數。

• n=0：H=1, L=0（初始）
• 每微秒：所有質點同時碰撞
• 高能 → 3 高能 + 1 低能
• 低能 → 2 高能 + 1 低能

得遞推：

H[n] = 3*H[n-1] + 2*L[n-1]
L[n] = 1*H[n-1] + 1*L[n-1]

矩陣形式

[H[n], L[n]]^T = M * [H[n-1], L[n-1]]^T

M = [[3, 2], [1, 1]]

[H[n], L[n]]^T = M^n * [1, 0]^T

矩陣快速冪模板

struct Matrix {
    long long a[2][2];
    Matrix() { memset(a, 0, sizeof(a)); }
    static Matrix identity() {
        Matrix I; I.a[0][0] = I.a[1][1] = 1; return I;
    }
};

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

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

完整代碼（含預計算版，n≤33 直接遞推更簡單）

#include <cstdio>
using namespace std;
typedef long long LL;

int main() {
    // 預計算 n=0..33
    LL H[34] = {1}, L[34] = {0};
    for (int i = 1; i <= 33; ++i) {
        H[i] = 3 * H[i-1] + 2 * L[i-1];
        L[i] = H[i-1] + L[i-1];
    }
    int n;
    while (scanf("%d", &n) == 1 && n != -1) {
        printf("%lld, %lld\n", H[n], L[n]);
    }
    return 0;
}

樣例驗證

總結

本題核心是建立正確的線性遞推關係。n ≤ 33 時直接預計算最簡潔；若 n 極大（如 10¹⁸），則需矩陣快速冪 O(log n)。遞推建模技巧：列出單步轉移規則，彙總為矩陣形式。注意初始條件 n=0 為 1 高能 0 低能，輸出格式為 %lld, %lld（逗號+空格）。