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

編輯：關於C語言

題目大意

遞推關係：

x < 10: f(x) = x
x ≥ 10: f(x) = Σ_{i=0}^{9} a_i · f(x-1-i)   (a_i ∈ {0,1})

給定 k (≤10⁹)、m，求 f(k) mod m。多組測試直到 EOF。

矩陣構造

狀態向量：[f(x), f(x-1), ..., f(x-9)]^T

轉移矩陣 10×10：

[ a0 a1 a2 ... a9 ]
[ 1  0  0  ... 0  ]
[ 0  1  0  ... 0  ]
[ ...            ]
[ 0  0  ... 1  0  ]

則 State(x) = M · State(x-1)，故 State(k) = M^{k-9} · State(9) (k≥10)。

完整 C++ 代碼


#include 
using namespace std;
typedef long long ll;

struct Matrix {
    int n, m;
    ll a[20][20];
    Matrix(int _n=0, int _m=0, bool ident=false) : n(_n), m(_m) {
        memset(a, 0, sizeof(a));
        if (ident) for (int i = 0; i < n; i++) a[i][i] = 1;
    }
    Matrix operator*(const Matrix& o) const {
        Matrix r(n, o.m);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < m; k++) if (a[i][k])
                for (int j = 0; j < o.m; j++) {
                    r.a[i][j] = (r.a[i][j] + a[i][k] * o.a[k][j]) % mod;
                }
        return r;
    }
};

ll mod, k;

Matrix mpow(Matrix a, ll p) {
    Matrix r(a.n, a.n, true);  // 單位矩陣
    while (p) {
        if (p & 1) r = r * a;
        a = a * a;
        p >>= 1;
    }
    return r;
}

int main() {
    while (cin >> k >> mod) {
        Matrix M(10, 10);
        for (int i = 0; i < 9; i++) M.a[i][i+1] = 1;  // 移位行
        for (int i = 0; i < 10; i++) {
            int x; cin >> x;
            M.a[9][i] = x;  // 係數行 (a0..a9 對應 a[9][0]..a[9][9])
        }
        
        if (k < 10) { cout << k % mod << '\n'; continue; }
        
        Matrix init(10, 1);
        for (int i = 0; i < 10; i++) init.a[i][0] = i;  // f(0)..f(9)
        
        Matrix Mp = mpow(M, k - 9);
        Matrix res = Mp * init;
        cout << res.a[9][0] % mod << '\n';
    }
    return 0;
}

關鍵點解析

環節	細節
矩陣維度	10×10 (遞推階數 10)
初始向量	[f(9), f(8), ..., f(0)]^T = [9,8,...,0]^T
冪次	k-9 (從 f(9) 推到 f(k) 需 k-9 步)
取模	矩陣乘法每步取模，防溢出
係數順序	輸入 a0..a9 對應矩陣最後一行 [a0,a1,...,a9]

矩陣乘法優化

稀疏優化：轉移矩陣只有 19 個非零元，可用結構體存非零位置
循環順序：i-k-j 順序利用緩存局部性，比 i-j-k 快
模運算：用 if (x >= mod) x -= mod; 替代 % 加速

複雜度分析

矩陣乘法：O(10³) = O(1000)
快速冪：O(log k) ≈ 30 步
單測試用例：~30,000 操作，極快
空間：O(10²) = O(100)

遞推與矩陣快速冪通用模板

線性遞推: f(n) = Σ c_i f(n-i)
狀態向量: [f(n), f(n-1), ..., f(n-k+1)]^T
轉移矩陣:
[ c1 c2 ... ck ]
[ 1  0  ... 0  ]
[ 0  1  ... 0  ]
[ ...        ]
[ 0  0  ... 1 0]
初始向量: [f(k-1), f(k-2), ..., f(0)]^T
目標: M^{n-k+1} * Init