← 所有文章
约 2 分钟

P3216 题解：[HNOI2011] 数学作业

把拼接写成递推，位数相同的数放在一起，用矩阵快速幂整段处理。

题解矩阵快速幂C++
本页目录
  1. 写成矩阵
  2. 按位数分段
  3. 主要代码

题目链接

把 11 到 nn 依次拼接，数会长得很快。不过我们只需要余数，可以边拼边取模。

记拼到 ii 时的结果为 aia_i。如果 ii 有 kk 位，就有

ai=ai−1×10k+i.a_i=a_{i-1}\times10^k+i.

写成矩阵

递推里用到了拼接结果和当前的 ii，再补一个常数 11，就能凑成行向量：

(ai−1i−11)(10k00110111)=(aii1).\begin{pmatrix} a_{i-1} & i-1 & 1 \end{pmatrix} \begin{pmatrix} 10^k & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} a_i & i & 1 \end{pmatrix}.

第一项得到 ai−1×10k+ia_{i-1}\times10^k+i，第二项从 i−1i-1 变成 ii，正好完成一次拼接。

按位数分段

一位数用同一个矩阵，两位数又用同一个矩阵。所以不用一个数一个数地算，可以让矩阵做快速幂，整段一起处理。

从 (0,0,1)(0,0,1) 出发，依次处理这些分段。完整的一段 kk 位数有 9×10k−19\times10^{k-1} 个，最后一段算到 nn 为止。处理完后，第一维就是答案。

主要代码

main.cpp
// count 是 n 的十进制位数
Matrix::Matrix<modint, 1, 3> unit = std::initializer_list<std::initializer_list<modint>>{{0, 0, 1}};
u64 pow10 = 1;
while (count --) {
    unit *= Matrix::Matrix3F<modint>{std::initializer_list<std::initializer_list<modint>>{{10 * pow10, 0, 0}, {1, 1, 0}, {1, 1, 1}}}.power(count ? 10 * pow10 - pow10 : n - pow10 + 1);
    pow10 *= 10;
}
std::cout << unit(0, 0) << "\n";
通过 RSS 订阅回到顶部 ↑