自动搬运

查看原文

来自洛谷，原作者为

	Laoshan_PLUS 海客谈瀛洲

搬运于2025-08-24 21:46:35，当前版本为作者最后更新于2024-03-13 21:30:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

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

对于 $100\%$ 的数据，$1\le n\le10^{18}$，$1\le m\le10^9$。

解析

矩阵加速题。令 $\textit{dp}[i]=\operatorname{Concatenate}(i)$，则有：

$$\textit{dp}[i]=\left[\left(\textit{dp}[i-1]\times10^{1+\lg i}\bmod m\right)+i\right]\bmod m $$

构造出答案矩阵：

$$\begin{bmatrix} \textit{dp}[i] \\ i+1 \\ 1 \end{bmatrix} $$

答案矩阵是如何构造的？

答案矩阵一般情况下都是单列：

1. 先把 $\textit{dp}[i]$ 写上，方便在最后直接输出：

$$\begin{bmatrix}\textit{dp}[i]\\ \\ \\\end{bmatrix} $$

2. 观察转移方程，$\textit{dp}[i]$ 需要由 $\textit{dp}[i-1]$ 和 $i$ 推出，这两项都需要体现在矩阵里。为了转移下一位，矩阵中还需要有 $i+1$：

$$\begin{bmatrix}\textit{dp}[i]\\i+1\\ \\\end{bmatrix} $$

3. 由 $i$ 是如何推得 $i+1$ 的呢？所以矩阵中还需要有一个常数项 $1$：

$$\begin{bmatrix}\textit{dp}[i]\\i+1\\1\end{bmatrix} $$

构造出转移矩阵：

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

$k$ 为这一步对应 $i$ 的数位数，即 $1+\lg i$。

转移矩阵是如何构造的？

转移矩阵构造法：将单行的答案矩阵横倒过来看，再根据状态转移方程处理每行的加减情况。

1. $\textit{dp}[i]$ 是如何推得的？$\textit{dp}[i]=\textit{dp}[i-1]\times10^{1+\lg i}+i$（取模在运算时体现）。令 $k=1+\lg i$，所以转移矩阵第一行写上：

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

2. 同理，要推 $i+1$，就得在 $i$ 的位置和 $1$ 的位置点上 $1$：

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

3. $1$ 转移过来还是 $1$，所以完成转移矩阵：

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

我们发现 $k$ 会随着 $i$ 改变，这在矩阵快速幂中是不允许的，因此不能一次矩阵快速幂解决。我们需要根据每一次的 $i$ 构造转移矩阵，每次快速幂的幂次这一层转移的次数，即 $\min\hspace{-0.25em}\left(n-10^{k-1}+1,10^k-10^{k-1}\right)$。

细节……也就这么多，具体见代码。时间复杂度 $O(\lg n\times\log n)$ 左右。

实现

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

int n, p;
struct Matrix {
	int r, c, mx[4][4];
	Matrix() {
		memset(mx, 0, sizeof(mx));
	}
	friend Matrix operator * (Matrix a, Matrix b) {
		Matrix res;
		res.r = min(a.r, b.r), res.c = min(a.c, b.c);
		for (int i = 1; i <= a.r; i++)
			for (int j = 1; j <= b.c; j++)
				for (int k = 1; k <= a.c; k++)
					res.mx[i][j] = (res.mx[i][j] + a.mx[i][k] * b.mx[k][j] % p) % p;
		return res;
	}
} a, b;

Matrix power(Matrix a, Matrix b, int x) {
	while (x > 0) {
		if (x & 1) a = b * a;
		b = b * b;
		x >>= 1;
	}
	return a;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n >> p;
	a.c = 1, a.r = b.r = b.c = 3;
	a.mx[2][1] = a.mx[3][1] = 1;
	b.mx[1][2] = b.mx[2][2] = b.mx[2][3] = b.mx[3][3] = 1;
	for (int k = 10;; k *= 10) {
		b.mx[1][1] = k % p;
		if (n < k) {
			a = power(a, b, n - k / 10 + 1);
			break;
		}
		a = power(a, b, k - k / 10);
	}
	cout << a.mx[1][1] << '\n';
	
	return 0;
}