HDU 1757 A Simple Math Problem：矩陣快速冪求線性遞迴第 k 項

題目大意

遞迴定義：

f(x) = x                    (x < 10)
f(x) = Σ_{i=0..9} a_i·f(x-1-i)  (x ≥ 10)

其中 a_i ∈ {0,1}。給定 k (≤10^9)、m，求 f(k) mod m。多組測資。

矩陣構造

狀態向量 [f(x), f(x-1), ..., f(x-9)]^T。轉移矩陣 10×10：

| 0 1 0 ... 0 |
| 0 0 1 ... 0 |
| .           |
| 0 0 0 ... 1 |
| a9 a8 ... a0|

則 V(x) = A · V(x-1)，V(k) = A^{k-9} · V(9)（k≥10）。

快速冪核心

Matrix mul(Matrix A, Matrix B, int mod) {
    Matrix C; C.n=A.n; C.m=B.m;
    for i,j,k: C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % mod;
    return C;
}

Matrix pow(Matrix A, long long k, int mod) {
    Matrix R; R.n=R.m=10; for i R[i][i]=1; // 單位矩陣
    while (k) {
        if (k&1) R = mul(R, A, mod);
        A = mul(A, A, mod);
        k >>= 1;
    }
    return R;
}

完整代碼

#include 
using namespace std;
typedef long long ll;

const int SZ = 10;
struct Matrix {
    int a[SZ][SZ];
    Matrix() { memset(a, 0, sizeof(a)); }
};

Matrix mul(const Matrix& A, const Matrix& B, int mod) {
    Matrix C;
    for (int i=0;i>= 1;
    }
    return R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll k; int mod;
    while (cin >> k >> mod) {
        Matrix A;
        for (int i=0;i<9;i++) A.a[i][i+1]=1;
        for (int i=0;i<10;i++) { int x; cin>>x; A.a[9][9-i]=x; } // a9..a0

        if (k < 10) { cout << (k%mod) << '\n'; continue; }

        Matrix B; // 初始向量 f(0)..f(9)
        for (int i=0;i<10;i++) B.a[i][0] = i;

        Matrix R = mpow(A, k-9, mod);
        R = mul(R, B, mod);
        cout << R.a[9][0] << '\n';
    }
    return 0;
}

複雜度與技巧

• 矩陣乘法 O(10^3)，快速冪 O(log k)，單測資極快。
• 初始向量 B 為列向量（10×1），結果取 R[9][0] 對應 f(k)。
• 模數 mod 每次測資不同，矩陣運算中每步取模。