「BZOJ2326」[HNOI2011]数学作业

Description

小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题:
给定正整数 NNMM ,要求计算Concatenate(1N)Concatenate (1 \cdots N) ModMod MM 的值,其中 Concatenate(1N)Concatenate (1 \cdots N) 是将所有正整数 1,2,,N1, 2, …, N 顺序连接起来得到的数。例如,N=13N = 13 , Concatenate(1N)=12345678910111213Concatenate (1 \cdots N)=12345678910111213 .小C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。

Input

只有一行且为用空格隔开的两个正整数N和M,

Output

仅包含一个非负整数,表示 Concatenate(1N)(modM)Concatenate (1 \cdots N) \pmod {M} 的值。

Sample Input

1
13 13

Sample Output

1
4

HINT

1N10181\leq N\leq 10^{18}1M1091\leq M\leq 10^9.

Solution

构造矩阵

[fnn1][log10(n+1)00110111]=[fn+1n+11]\begin{bmatrix}f_n & n & 1 \end{bmatrix}\begin{bmatrix}log_{10}(n+1) & 0 & 0\\1 & 1 & 0\\ 1 & 1 & 1\end{bmatrix}=\begin{bmatrix}f_{n+1} & n+1 & 1 \end{bmatrix}

但是转移矩阵跟左边大小有关,我们可以枚举位数来分块计算。
[1,9],[10,99],[100,999],[10k,10k+11][1,9],[10,99],[100,999],[10^k,10^{k+1}-1]
那么每一次计算的转移矩阵就是

[t00110111]\begin{bmatrix}t & 0 & 0\\1 & 1 & 0\\ 1 & 1 & 1\end{bmatrix}

其中tt就是枚举的位数10k10^k
时间复杂度大概是33(logn)23^3(logn)^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef unsigned long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
ll p;
struct Matrix {
ll a[3][3];
Matrix(){memset(a,0,sizeof a);}
Matrix operator *(const Matrix b) {
Matrix c;
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j)
for(int k = 0; k < 3; ++k)
(c.a[i][j] += a[i][k] * b.a[k][j] % p) %= p;
return c;
}
};
ll n;
ll ksm(ll x, ll y) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x % p;
return res;
}
Matrix solve(ll s, ll t, ll d) {
Matrix res, b;
res.a[0][0] = s % p;
res.a[0][1] = s % p;
res.a[0][2] = 1;

b.a[0][0] = d % p;
b.a[1][0] = 1;
b.a[2][0] = 1;

b.a[1][1] = 1;
b.a[2][1] = 1;

b.a[2][2] = 1;
for(ll y = t - s; y; y >>= 1, b = b * b)
if(y & 1) res = res * b;
return res;
}
int main() {
n = read(), p = read();
ll t = 1;
ll ans = 0;
while(t <= n) {
ll E = min(t * 10 - 1, n);
Matrix res = solve(t, E, t * 10 % p);
ans = (ans * ksm(t*10 % p, E - t + 1) % p + res.a[0][0]) %p;
t *= 10;
}
writeln(ans);
return 0;
}