UVA 580 Critical Mass：遞推關係與矩陣快速冪

題目背景

中國環遊戲：n 個環套在棍子上，第一個環可隨意取放，第 x 個環 (x>1) 取放條件是第 x-1 個環已套上且前 x-2 個環全未套。求將 n 個環全取下的最少操作次數。

遞推推導

設 f(n) 為取下前 n 個環的最少步數。最優策略：先取下第 n 個環（需前 n-2 個全取下，再放上第 n-1 個），共 f(n-2)+1 步；此時狀態為前 n-2 全無、第 n-1 有、第 n 無。接著取下第 n-1 個環（需先放上前 n-2 個），又需 f(n-2) 步；最後取下前 n-1 個環需 f(n-1) 步。得遞推：
f(n) = f(n-1) + 2*f(n-2) + 1，初值 f(1)=1, f(2)=2。
用矩陣快速冪優化至 O(log n)。

代碼 (C++)

#include <cstdio>
#include <cstring>
const int MOD = 200907;
struct Mat { long long g[3][3]; } ori, res;
long long n;

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

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

int main() {
    while (scanf("%lld", &n) == 1 && n) {
        if (n == 1 || n == 2) { printf("%lld\n", n); continue; }
        memset(ori.g, 0, sizeof(ori.g));
        memset(res.g, 0, sizeof(res.g));
        ori.g[0][0] = 2; ori.g[0][1] = ori.g[0][2] = 1;
        res.g[0][0] = res.g[0][1] = res.g[2][0] = res.g[2][2] = 1;
        res.g[1][0] = 2;
        power(n - 2);
        printf("%lld\n", ori.g[0][0]);
    }
    return 0;
}