HDU 1757 A Simple Math Problem：矩陣快速冪解線性遞推

問題描述

遞推函數 f(x)：

• x < 10 時 f(x) = x
• x ≥ 10 時 f(x) = Σ_{i=0}^{9} a_i f(x-1-i)，其中 a_i ∈ {0,1}

給定 k (< 2e9), m (< 1e5) 和 a_0..a_9，求 f(k) % m。

矩陣構造

定義狀態向量 V_x = [f(x), f(x-1), ..., f(x-9)]^T（10 維）。則 V_{x+1} = M * V_x，轉移矩陣 M 為：

M = [ a_0 a_1 ... a_9 ]
    [ 1   0   ... 0   ]
    [ 0   1   ... 0   ]
    [ ...           ]
    [ 0   0   ... 1 0 ]

即第一行為係數 a_0..a_9，下方為單位矩阵右移，實現遞推滾動。

快速冪計算

初始向量 V_9 = [9,8,...,0]^T（因 f(i)=i for i<10）。

對於 k ≥ 10，V_k = M^{k-9} * V_9。答案為結果向量第一個分量 % m。

矩陣乘法模 m，快速冂 O(log k)，矩陣維度固定 10，常數極小。

代碼關鍵點

• 用 __int64（或 long long）存儲中間乘積，模 m 後回 int。
• 矩陣乘法三重循環，優化：if (a[i][j]) for k ... 跳過零係數。
• k < 10 直接輸出 k % m。

完整參考代碼

#include <cstdio>
#include <cstring>
using namespace std;
struct Mat { long long a[10][10]; };
Mat mul(Mat A, Mat B, int mod) {
    Mat C; memset(C.a,0,sizeof(C.a));
    for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(A.a[i][j])
        for(int k=0;k<10;k++)
            C.a[i][k] = (C.a[i][k] + A.a[i][j]*B.a[j][k]) % mod;
    return C;
}
Mat qpow(Mat base, long long exp, int mod) {
    Mat res; memset(res.a,0,sizeof(res.a));
    for(int i=0;i<10;i++) res.a[i][i]=1;
    while(exp){
        if(exp&1) res=mul(res,base,mod);
        base=mul(base,base,mod);
        exp>>=1;
    }
    return res;
}
int main(){
    long long k; int m, a[10];
    while(scanf("%lld%d",&k,&m)==2){
        for(int i=9;i>=0;i--) scanf("%d",&a[i]); // 注意輸入順序 a0..a9 對應 a[0]..a[9]
        if(k<10){ printf("%lld\n",k%m); continue; }
        Mat M; memset(M.a,0,sizeof(M.a));
        for(int j=0;j<10;j++) M.a[0][j]=a[j];
        for(int i=1;i<10;i++) M.a[i][i-1]=1;
        Mat R = qpow(M, k-9, m);
        long long ans=0;
        for(int i=0;i<10;i++) ans = (ans + R.a[0][i] * (9-i)) % m; // V_9 = [9,8,...,0]
        printf("%lld\n",ans);
    }
    return 0;
}

總結

HDU 1757 是線性遞推 + 矩陣快速冂的標準模板題，關鍵在於正確構造伴隨矩陣並處理初始向量，模數非質數不影響矩陣乘法。