P3216 题解：数字拼接也能用矩阵快速幂

题目链接。把 $1,2,\ldots,n$ 依次拼起来，求这个大整数模 $m$ 的余数。

拼上一个 $k$ 位数，就是原结果乘 $10^k$ 再加它，全程可以取模。 $n$ 很大时，再用矩阵快速幂跳过逐个拼接。

状态里为什么还要放当前数字

记拼到 $i$ 的结果为 $a_i$ ，若 $i$ 有 $k$ 位，则

a_i=10^k a_{i-1}+i.

只有 $a_i$ 还不够，因为加上的 $i$ 每次也在变化。把当前数字一起放进状态，再补一个常数 $1$ ，就能表达“加一”：

\begin{pmatrix}a_{i-1}&i-1&1\end{pmatrix} \underbrace{\begin{pmatrix} 10^k&0&0\\ 1&1&0\\ 1&1&1 \end{pmatrix}}_{T_k} =\begin{pmatrix}a_i&i&1\end{pmatrix}.

同一位数的数字，用同一个矩阵

同一位数段内 $T_k$ 不变，连续拼接 $t$ 个数，就右乘 $T_k^t$ 。例如拼到 $13$ ：

(0,0,1)\,T_1^9\,T_2^4.

从状态 $(0,0,1)$ 出发，按顺序处理每一段。一般地， $k$ 位数这一段从 $10^{k-1}$ 到 $\min(n,10^k-1)$ ，两端都包含，所以次数是“右端点 − 左端点 + 1”。

处理完后，状态第一项就是答案。

代码

下面给出独立实现，按题目的 $n\le10^{18}$ 、 $m\le10^9$ 使用 64 位整数。lo * 10 用无符号 64 位保存，避免在最后一组计算 $10^{19}$ 时超出有符号范围。

展开完整实现（输入 n 和 m）

#include <algorithm>
#include <array>
#include <iostream>

using u64 = unsigned long long;
using Mat = std::array<std::array<long long, 3>, 3>;
long long mod;

Mat multiply(const Mat& a, const Mat& b) {
    Mat c{};
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}

Mat power(Mat a, u64 e) {
    Mat result{};
    for (int i = 0; i < 3; ++i) result[i][i] = 1;
    while (e) {
        if (e & 1) result = multiply(result, a);
        a = multiply(a, a);
        e >>= 1;
    }
    return result;
}

int main() {
    u64 n;
    std::cin >> n >> mod;
    Mat state{};
    state[0][2] = 1;
    for (u64 lo = 1; lo <= n; lo *= 10) {
        u64 hi = std::min(n, lo * 10 - 1);
        Mat t{{{{static_cast<long long>(lo * 10 % mod), 0, 0}},
               {{1, 1, 0}}, {{1, 1, 1}}}};
        state = multiply(state, power(t, hi - lo + 1));
    }
    std::cout << state[0][0] << '\n';
}

每段对固定的 $3\times3$ 矩阵做快速幂，保守计总时间 $O(\log^2 n)$ 、额外空间 $O(1)$ 。可以用 $n=9,10,13$ 对照逐个拼接，检查跨位数边界和最后一段的长度。