Jinglei's blog
0%

「HNOI 2011」数学作业

Posted on Edited on

题目链接：https://www.luogu.com.cn/problem/P3216

题面

题目描述

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

给定正整数 n,mn,m，要求计算 Concatenate(n) mod  m\text{Concatenate}(n) \bmod \ m 的值，其中 Concatenate(n)\text{Concatenate}(n) 是将 1∼n1 \sim n 所有正整数 顺序连接起来得到的数。

例如，n=13n = 13 , Concatenate(n)=12345678910111213\text{Concatenate}(n) = 12345678910111213。小C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入格式

一行两个正整数 n,mn,m。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
13 13

样例输出 #1

1
4

提示

【数据范围】
对于 30%30\% 的数据，1≤n≤1061\le n \le 10^6；
对于 100%100\% 的数据，1≤n≤10181\le n \le 10^{18}，1≤m≤1091\le m \le 10^9。

思路——矩阵加速

首先，我们可以写出一个看起来没有任何用处的递推式：Concatenate(n)=Concatenate(n−1)∗10k+n\text{Concatenate}(n) = \text{Concatenate}(n-1)*10^k+n ，其中 kk 是 nn 的位数，即 ⌈log⁡10k⌉\left \lceil\log_{10}k\right \rceil 。

这个递推式肯定不能直接推，毕竟 1≤n≤10181\le n \le 10^{18} 的数据范围。于是想到可以使用矩阵加速。

我们可以构造出一个这样的，包含答案的矩阵：

[Concatenate(n)n1]\begin{bmatrix}\text{Concatenate}(n)\\ n\\ 1\end{bmatrix}

第一行和第二行都很好理解，第三行为什么要加一个 11 进去呢？这是因为我们一定是要从 n−1n-1 转移到 nn 的，而第二行的 n−1n-1 要想变成 nn ，一定是需要加上一个常数 11 的。

于是，根据这个，以及上面的递推式，我们可以推出这个式子：

[10k11011001]∗[Concatenate(n−1)n−11]=[Concatenate(n)n1]\begin{bmatrix}10^k &1 &1 \\ 0 &1 &1 \\ 0 &0 &1 \end{bmatrix}*\begin{bmatrix}\text{Concatenate}(n-1)\\ n-1\\ 1\end{bmatrix} = \begin{bmatrix}\text{Concatenate}(n)\\ n\\ 1\end{bmatrix}

实际操作中，我会把后两个矩阵写好，然后根据递推式再一行一行写出转移矩阵，也就是第一个。

由于这里的 kk 是和 nn 相关的，我们需要从小到大枚举 kk ，分段矩阵快速幂。

避坑——顺序那些事

我们都知道，矩阵乘法的结合律成立，而交换律是不成立的，也就是说对于两个矩阵 AA 和 BB ，A∗B≠B∗AA*B \neq B*A 。这道题由于需要分段快速幂，所以需要特别注意乘法的顺序。

就拿样例数据举例，n=13n=13 时，我们把这个式子展开，是这个样子的：

[10211011001]4∗([10111011001]8∗[Concatenate(1)11])=([10211011001]4∗[10111011001]8)∗[Concatenate(1)11]=[Concatenate(n)n1]\begin{bmatrix} 10^2 &1 &1 \\ 0 &1 &1 \\ 0 &0 &1 \end{bmatrix}^4*\left ( \begin{bmatrix} 10^1 &1 &1 \\ 0 &1 &1 \\ 0 &0 &1 \end{bmatrix}^8*\begin{bmatrix} \text{Concatenate}(1)\\ 1\\ 1 \end{bmatrix} \right ) = \left (\begin{bmatrix} 10^2 &1 &1 \\ 0 &1 &1 \\ 0 &0 &1 \end{bmatrix}^4* \begin{bmatrix} 10^1 &1 &1 \\ 0 &1 &1 \\ 0 &0 &1 \end{bmatrix}^8 \right )*\begin{bmatrix} \text{Concatenate}(1)\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} \text{Concatenate}(n)\\ n\\ 1 \end{bmatrix}

在我们通过结合律结合各阶段的转移矩阵的时候，如果像我这样要把转移矩阵放在左边，要注意乘的时候顺序从右向左 kk 递减，这样在结合律之后才能得到原始的式子，也就是说要写成：

1
ans = k*ans

同时要注意边界问题——从 1 开始的话，转移到 9 只需要转移矩阵的 8 次幂，9 转移到 10 属于下一个阶段（因为 10 已经是两位了）。

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <iostream>

const int Maxn = 5;
typedef long long lol;
int Mod;
struct Matrix{
	int n, m;
	lol val[Maxn][Maxn] = {0};
}trans, anss, ii, init, tmp;
lol n;
Matrix qpow(Matrix, lol);
lol pow(int, int);

Matrix operator*(const Matrix&x, const Matrix&y){
	Matrix ans; ans.n = x.n; ans.m = y.m;
	lol tmp;
	for(int i=0; i<x.n; i++){
		for(int j=0; j<y.m; j++){
			tmp = 0;
			for(int k=0; k<x.m; k++){
				tmp += ((x.val[i][k]%Mod)*(y.val[k][j]%Mod))%Mod;
				tmp %= Mod;
			}
			ans.val[i][j] = tmp;
		}
	}
	return ans;
}

int main(){
//	freopen("data.in", "r", stdin);

	ii.n = 3; ii.m = 3;
	anss.n = 3; anss.m = 3;
	for(int i=0; i<3; i++){
		ii.val[i][i] = 1;
		anss.val[i][i] = 1;
	}

	trans.n = 3; trans.m = 3;
	trans.val[0][1] = 1; trans.val[0][2] = 1; trans.val[1][1] = 1; trans.val[1][2] = 1; trans.val[2][2] = 1;
	init.n = 3; init.m = 1;
	init.val[0][0] = 1; init.val[1][0] = 1; init.val[2][0] = 1;
	scanf("%lld %d", &n, &Mod);
//	n--;

	for(int i=1; i<=18; i++){
		if(n>=pow(10, i)){
			trans.val[0][0] = pow(10, i);
			if(i==1){
				anss = qpow(trans, pow(10, i)-pow(10, i-1)-1) * anss;
//				printf("%d %lld ", i, pow(10, i)-pow(10, i-1)-1);
			}
			else{
				anss = qpow(trans, pow(10, i)-pow(10, i-1)) *anss;
//				printf("%d %lld ", i, pow(10, i)-pow(10, i-1));
			}
			tmp = anss * init;
//			printf("%d\n", tmp.val[0][0]);
		}
		else{
			trans.val[0][0] = pow(10, i);
			n -= pow(10, i-1)-1;
			anss = qpow(trans, n)*anss;
//			printf("%d %lld\n", i, n);
			break;
		}
	}
	
	anss = anss * init;
	printf("%lld", anss.val[0][0]);

	return 0;
}

Matrix qpow(Matrix x, lol b){
	Matrix base = x, ans = ii;
	while(b){
		if(b & 1){
			ans = ans * base;
		}
		base = base * base;
		b >>= 1;
	}
	return ans;
}

lol pow(int a, int b){
	lol ans = 1;
	for(int i=0; i<b; i++){
		ans *= a;
	}
	return ans;
}