P3216 [HNOI2011] 数学作业 题解
Laoshan_PLUS
·
·
题解
题意
令 \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}
答案矩阵是如何构造的？
答案矩阵一般情况下都是单列：
- 先把 \textit{dp}[i] 写上，方便在最后直接输出：
\begin{bmatrix}\textit{dp}[i]\\ \\ \\\end{bmatrix}
- 观察转移方程，\textit{dp}[i] 需要由 \textit{dp}[i-1] 和 i 推出，这两项都需要体现在矩阵里。为了转移下一位，矩阵中还需要有 i+1：
\begin{bmatrix}\textit{dp}[i]\\i+1\\ \\\end{bmatrix}
- 由 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}
> 转移矩阵是如何构造的？
>
> **转移矩阵构造法：将单行的答案矩阵横倒过来看，再根据状态转移方程处理每行的加减情况。**
>
> 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)$ 左右。
### 实现
```cpp
#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;
}
```