ZOJ 3690 Choosing Number：矩陣快速冪計算合法序列數

問題描述

n 個人依次選擇 1..m 中的數。相鄰兩人選的數不能同時 > k。求合法選擇方案數模 1e9+7。n, m, k ≤ 10^9？實際 n≤10^9, m,k≤10^9。

狀態定義與遞推

設 F(i)：前 i 人中第 i 人選 > k 的方案數。
G(i)：前 i 人中第 i 人選 ≤ k 的方案數。
遞推：

F(i) = F(i-1)*(m-k) + G(i-1)*(m-k)
G(i) = F(i-1)*k + G(i-1)*(k-1)

初始：F(1) = m-k, G(1) = k。
答案 = F(n) + G(n)。

矩陣快速冪

將遞推寫為矩陣乘法：

[F(i)]   [m-k  m-k] [F(i-1)]
[G(i)] = [k    k-1] [G(i-1)]

計算 M^(n-1) * [F(1), G(1)]^T，取和模 MOD。

參考代碼

#include 
using namespace std;
const long long MOD = 1000000007;

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] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
    return C;
}

Matrix pow(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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m, k;
    while (cin >> n >> m >> k) {
        Matrix M;
        M.a[0][0] = M.a[0][1] = (m - k) % MOD;
        M.a[1][0] = k % MOD;
        M.a[1][1] = (k - 1) % MOD;
        Matrix R = pow(M, n - 1);
        long long F1 = (m - k) % MOD, G1 = k % MOD;
        long long Fn = (R.a[0][0] * F1 + R.a[0][1] * G1) % MOD;
        long long Gn = (R.a[1][0] * F1 + R.a[1][1] * G1) % MOD;
        cout << (Fn + Gn) % MOD << '\n';
    }
    return 0;
}

關鍵細節

• 矩陣乘法順序：C = A * B 對應先變換 B 再 A，此處遞推為左乘矩陣，故 M^(n-1) 正確。
• 取模：每步乘法後取模，防溢出（用 long long，乘積 < 1e18 < 2^63）。
• n=1 時 pow(M,0) 返回單位陣，答案 = F1+G1 = m，正確。

複雜度

矩陣冪 O(log n) 乘法，每乘法 8 次模乘，極快。

總結

ZOJ 3690 是矩陣快速冪經典應用：將線性遞推轉化為矩陣乘冪，O(log n) 求第 n 項。掌握「狀態定義 → 遞推 → 矩陣構造 → 快速冪」標準流程，可解決所有線性遞推大 n 求值問題。