HDU 4549 M-斐波那契數列：矩陣快速冪與歐拉定理取模

問題描述

定義數列：F[0]=a, F[1]=b, F[n]=F[n-1] × F[n-2] (n>1)。求 F[n] mod 1,000,000,007。a,b,n ≤ 10⁹。

指數規律與矩陣快速冪

觀察可得：F[n] = a^f_n-1 × b^f_n，其中 f 為標準斐波那契數列（f[0]=0, f[1]=1）。證明：取對數後滿足斐波那契遞推。

故問題轉化為求 f[n] 和 f[n-1] 模 φ(1,000,000,007) = 1,000,000,006（模數為質數，歐拉定理）。用 2×2 矩陣快速冪：

M = [[1,1],[1,0]], M^k = [[f_k+1, f_k], [f_k, f_k-1]]

算法步驟

1. 若 n=0 輸出 a；n=1 輸出 b。
2. 計算 M^n-1 mod 1,000,000,006，得到 f[n] 和 f[n-1]。
3. 快速冪計算 a^f[n-1] mod 1,000,000,007 和 b^f[n] mod 1,000,000,007。
4. 相乘取模輸出。

代碼關鍵部分

const long long MOD = 1000000007;
const long long PHI = MOD - 1; // 1000000006

struct Mat { long long a[2][2]; };

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

Mat pow(Mat base, long long exp) {
    Mat r; memset(r.a, 0, sizeof(r.a));
    r.a[0][0]=r.a[1][1]=1;
    while (exp) {
        if (exp&1) r = mul(r, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return r;
}

long long mod_pow(long long a, long long e) {
    long long r=1;
    while (e) {
        if (e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

總結

HDU 4549 結合了矩陣快速冪求斐波那契數、歐拉定理降低指數模、模冪運算。關鍵洞察是識別出指數遞推關係，並利用模數為質數的性質應用費馬小定理（歐拉定理特例）。