求将 \(1\) 到 \(n\) 的所有整数顺序连接得到的数模 \(m\) 的值
\(n\leq10^{18},\ m\leq10^9\)
矩阵加速
首先得到 \(f_i=10^{\lfloor \log_{10}i\rfloor}\times f_{i-1}+i\)
形如 \(f_i=k\times f_{i-1}+i\) 的式子显然可以矩阵加速，即表示为 \[\begin{bmatrix}f_i&i&1\end{bmatrix}\begin{bmatrix}k&0&0\\1&1&0\\1&1&1\end{bmatrix}=\begin{bmatrix}f_{i+1}&i+1&1\end{bmatrix}\]
又因为 \(10^{\lfloor\log_{10}i\rfloor}\) 的取值只有 \(18\) 种，于是可以将每种取值分类讨论
即求出后 \(f_{10^a-1}\) 通过矩阵 \(\begin{bmatrix}10^{a+1}&0&0\\1&1&0\\1&1&1\end{bmatrix}\) 快速转移至 \(f_{10^{a+1}-1}\) ，多出来的部分同理计算即可
计算过程可能会爆 \(long\ long\) ……
时间复杂度 \(O(\log_{10}{n}\times\log_2n)\)
代码（码风极丑……
#includeusing namespace std;#define rep(i) for (int i = 0; i < 3; i++)typedef long long ll;ll n; int P;struct matrix { int arr[3][3]; matrix() { memset(arr, 0, sizeof arr); } int* operator [] (const int& pos) { return arr[pos]; }} E, M;inline int inc(int x, int y) { return x + y < P ? x + y : x + y - P;}matrix operator + (matrix a, matrix b) { rep(i) rep(j) a[i][j] = inc(a[i][j], b[i][j]); return a;}matrix operator * (matrix a, matrix b) { matrix res; rep(k) rep(i) rep(j) { res[i][j] = inc(res[i][j], 1ll * a[i][k] * b[k][j] % P); } return res;}matrix qp(matrix a, ll k) { matrix res = E; for (; k; k >>= 1, a = a * a) { if (k & 1) res = res * a; } return res;}int main() { E[0][0] = E[1][1] = E[2][2] = 1; M[1][0] = M[1][1] = M[2][0] = M[2][1] = M[2][2] = 1; scanf("%lld %d", &n, &P); int f[15]; f[0] = 0; for (int i = 1; i < 10; i++) { f[i] = (10ll * f[i - 1] + i) % P; } if (n < 10) { printf("%d", f[n]); return 0; } matrix A; unsigned long long now = 10; A[0][0] = f[9], A[0][1] = 9, A[0][2] = 1; for (; now * 10 - 1 <= n; now *= 10) { M[0][0] = now * 10 % P; A = A * qp(M, now * 9); } M[0][0] = now * 10 % P; A = A * qp(M, n - now + 1); printf("%d", A[0][0]); return 0;}