洛谷P3216 [HNOI2011]数学作业 题解

题目链接：P3216 [HNOI2011]数学作业

题意：

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

给定正整数 $n,m$，要求计算 $\text{Concatenate}(n) \bmod \ m$ 的值，其中 $\text{Concatenate}(n)$ 是将 $1 \sim n$ 所有正整数 顺序连接起来得到的数。

例如，$n = 13$ , $\text{Concatenate}(n) = 12345678910111213$。

小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入格式：

一行两个正整数 $n,m$。

输出格式：

输出一行一个整数表示答案。

数据范围：

$1\le n \le 10^{18},~1\le m \le 10^9$。

设 $f_{i}$ 表示前 $i$ 个数拼起来的答案，则

$$\large f_{i} = f_{i-1} \times 10^{\left\lfloor\lg i\right\rfloor + 1} + i$$

注意到 $n$ 很大，考虑使用矩阵快速幂加速dp。

考虑构建递推矩阵

$$A=\begin{bmatrix}f_{n}&n&1\end{bmatrix}$$

初始矩阵为 $n=0$ 时。

转移矩阵就有点麻烦了，关键在于这个对数不好搞

但是注意到数字位数最多不超过 $18$ ，并且函数 $k = \left\lfloor\lg i\right\rfloor + 1$ 呈块状分布。

考虑使用分块的思想，固定一个 $k$ ，则转移矩阵如下：

$$M = \begin{bmatrix} 10^k & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$$

需要注意的是可能会爆 long long 。

时间复杂度 $\mathcal{O}(3^3\log^2 n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int mod;
void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
mat mul(mat A, mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
        {
            __int128 t = 0;
            for(int k = 0; k < m; k++) t += (__int128)A[i][k] * B[k][j];
            add(C[i][j], t % mod);
        }
    return C;
}
mat qpow(mat A, int b)
{
    int n = max(A.size(), A[0].size());
    mat ans(n, vector<int>(n));
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
void calc(mat &res, int p, int b)
{
    mat M(3, vector<int>(3));
    M[0][0] = p; M[1][0] = M[1][1] = M[2][0] = M[2][1] = M[2][2] = 1;
    res = mul(res, qpow(M, b));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, r = 10; cin >> n >> mod;
    mat res(1, vector<int>(3)); res[0][2] = 1;
    for(; r <= n; r = (r << 3) + (r << 1)) calc(res, r, r - (r / 10));
    calc(res, r, n - (r / 10) + 1); cout << res[0][0] << '\n';
    return 0;
}

---

参考文献：

[1] https://siyuan.blog.luogu.org/solution-p3216