洛谷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;
}
参考文献: