HDU 3306 Another kind of Fibonacci：4×4 矩陣快速冪

遞推關係與矩陣構造

給定遞推式，構造 4×4 轉移矩陣將狀態向量 [F_n, F_n-1, F_n-2, F_n-3]^T 線性變換。通過快速冪將 O(n) 降為 O(log n)。

關鍵代碼

const int MOD = 10007;
int a[4][4], p[4][4], tmp[4][4];

void mul(int A[4][4], int B[4][4], int C[4][4]) { // C = A * B
    memset(C, 0, sizeof(C));
    for (int i=0;i<4;++i)
        for (int k=0;k<4;++k)
            if (A[i][k])
                for (int j=0;j<4;++j)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
}

void power(long long n) {
    // p = identity, a = base matrix
    while (n) {
        if (n & 1) mul(p, a, tmp), memcpy(p, tmp, sizeof(p));
        mul(a, a, tmp), memcpy(a, tmp, sizeof(a));
        n >>= 1;
    }
}

狀態向量初始化

根據題目邊界條件設定初始向量 ans[4] = {2, 1, 1, 1}，最終結果為 res[0]。

模板優化提示

• 矩陣乘法內層判斷 if (A[i][k]) 跳過零元素
• 用 memcpy 替換逐元素賦值
• 模數較小時可用 int，大模數改 long long