UVA 12470：Tribonacci 數列矩陣快速冪

題目

遞推 f(n) = f(n-1) + f(n-2) + f(n-3)，f(1)=0, f(2)=1, f(3)=2。求 f(n) 模 1,000,000,009。n 可大。

矩陣構造

狀態向量 [f(n), f(n-1), f(n-2)]^T。轉移矩陣：

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

初始 [f(3), f(2), f(1)]^T = [2,1,0]^T。計算 M^(n-3) * init 取第一分量。n≤3 直接返回。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
struct Mat { long long a[3][3]; };
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;
}
Mat power(Mat base, long long exp) {
    Mat res; memset(res.a,0,sizeof(res.a));
    for(int i=0;i<3;i++) res.a[i][i]=1;
    while(exp){ if(exp&1) res=mul(res,base); base=mul(base,base); exp>>=1; }
    return res;
}
int main() {
    long long n;
    while(scanf("%lld",&n)==1 && n) {
        if(n<=3){ printf("%lld\n", n-1); continue; }
        Mat M = {{{1,1,1},{1,0,0},{0,1,0}}};
        Mat R = power(M, n-3);
        long long ans = (R.a[0][0]*2 + R.a[0][1]*1 + R.a[0][2]*0) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}