BZOJ 2326 HNOI 2011 數學作業：矩陣快速冪加速字串拼接取模

題目大意

求字串 "12345678910111213..."（自然數順序拼接）前 k 位數字構成的整數對 m 取模的值。k 可大至 10¹⁸。

矩陣建模

觀察拼接過程：當前數值 X，下一個數 y，位數 len，新值 X' = X × 10^len + y。
同一數量級（如兩位數 10~99）的 len 固定，y 依次遞增 1。可構造狀態向量 [X, y, 1]，轉移矩陣：

[ 10^len   1   0 ]   [ X ]   [ X' ]
[   0      1   1 ] × [ y ] = [ y+1 ]
[   0      0   1 ]   [ 1 ]   [  1  ]

對每個數量級區間（1~9, 10~99, 100~999...），用矩陣快速冪跳過整個區間。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int64 MOD;

struct Mat {
    int64 a[3][3];
    Mat(bool ident = false) { memset(a, 0, sizeof(a)); if (ident) a[0][0]=a[1][1]=a[2][2]=1; }
    Mat operator*(const Mat& o) const {
        Mat r;
        for (int i=0;i<3;++i) for (int k=0;k<3;++k) if (a[i][k])
            for (int j=0;j<3;++j) r.a[i][j] = (r.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return r;
    }
};

Mat mpow(Mat base, int64 exp) {
    Mat r(true);
    while (exp) { if (exp & 1) r = r * base; base = base * base; exp >>= 1; }
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int64 k; cin >> k >> MOD;
    int64 ans = 0, cur = 10; // 當前數量級起始數 (10, 100, ...)
    while (k >= cur - cur/10 && cur < (int64)1e18) {
        int64 cnt = cur - cur/10; // 本數量級個數
        Mat trans; trans.a[0][0] = cur % MOD; trans.a[0][1] = 1; trans.a[1][1] = 1; trans.a[1][2] = 1; trans.a[2][2] = 1;
        trans = mpow(trans, cnt);
        Mat vec; vec.a[0][0] = ans; vec.a[0][1] = (cur/10) % MOD; vec.a[0][2] = 1;
        ans = (vec * trans).a[0][0];
        cur *= 10;
    }
    // 處理最後不完整數量級
    if (k > 0) {
        Mat trans; trans.a[0][0] = cur % MOD; trans.a[0][1] = 1; trans.a[1][1] = 1; trans.a[1][2] = 1; trans.a[2][2] = 1;
        trans = mpow(trans, k);
        Mat vec; vec.a[0][0] = ans; vec.a[0][1] = (cur/10) % MOD; vec.a[0][2] = 1;
        ans = (vec * trans).a[0][0];
    }
    cout << ans << '\n';
    return 0;
}

複雜度

• 數量級數 ≤ 18（k ≤ 10¹⁸），每級矩陣冪 O(log cnt)，矩陣乘法 O(3³)，總時間極快。
• 空間：O(1)。

關鍵點

• 狀態向量包含 1 以處理常數項 y 的遞增。
• 模數 MOD 非固定，需作為全局變量傳入矩陣運算。
• 邊界：cur 可能溢出 64 位，循環條件 cur < 1e18 防護。