HDU 2842：中國環遊戲 - 矩陣快速冪優化遞推

題目重述

同 UVA 580：n 個環，操作規則相同，求全部取下的最少步數模 200907。n 可達 10^18，需矩陣快速冪。

遞推與矩陣構造

遞推：f(n) = f(n-1) + 2f(n-2) + 1，f(1)=1, f(2)=2。
構造狀態向量 [f(n), f(n-1), 1]^T，轉移矩陣：

[1 2 1]
[1 0 0]
[0 0 1]

初始向量 [f(2), f(1), 1]^T = [2, 1, 1]^T。計算 M^(n-2) * init 取第一分量。

代碼 (C++)

#include <cstdio>
#include <cstring>
const int MOD = 200907;
struct Mat { long long a[3][3]; } base, ans;
long long n;

Mat mul(Mat x, Mat y) {
    Mat r; memset(r.a, 0, sizeof(r.a));
    for (int i = 0; i < 3; i++)
        for (int k = 0; k < 3; k++)
            for (int j = 0; j < 3; j++)
                r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
    return r;
}

void power(long long p) {
    while (p) {
        if (p & 1) ans = mul(ans, base);
        base = mul(base, base);
        p >>= 1;
    }
}

int main() {
    while (scanf("%lld", &n) == 1 && n) {
        if (n == 1 || n == 2) { printf("%lld\n", n); continue; }
        memset(base.a, 0, sizeof(base.a));
        memset(ans.a, 0, sizeof(ans.a));
        // 單位矩陣
        for (int i = 0; i < 3; i++) ans.a[i][i] = 1;
        base.a[0][0] = 1; base.a[0][1] = 2; base.a[0][2] = 1;
        base.a[1][0] = 1; base.a[2][2] = 1;
        power(n - 2);
        long long res = (ans.a[0][0]*2 + ans.a[0][1]*1 + ans.a[0][2]*1) % MOD;
        printf("%lld\n", res);
    }
    return 0;
}