![[HNOI2011]数学作业 --- 矩阵优化](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[HNOI2011]数学作业 --- 矩阵优化")
[HNOI2011]数学作业
题目描述：
小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：
给定正整数 N 和 M ，要求计算\(Concatenate(1..N)\; Mod\; M\) 的值，
其中 \(Concatenate(1..N)\) 是将所有正整数 1, 2, …, N顺序连接起来得到的数。
例如，N = 13; \(Concatenate( 1..13) = 12345678910111213\)
小C 想了大半天终于意识到这是一道不可能手算出来的题目
于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。
输入格式：
输入文件只有一行且为用空格隔开的两个正整数N和M，
其中30%的数据满足1 ≤ N ≤ \(10^{7}\)；
100%的数据满足1 ≤ N ≤ \(10^{18}\) 且1 ≤ M ≤ \(10^{9}\)
输出格式：
一行，表示\(Concatenate(1..N)\; Mod\; M\)
30分暴力就不谈了
考虑公式化表达
记 \(f[i]\) 为考虑到第 i 个数字的值
那么有转移式
\(f[i] = f[i - 1]*10^{len(i)}+i\)
一个非常漂亮的递推式，不是吗？
很自然地想到用矩阵来优化。
但是，\(10^{len(i)}\)无法在矩阵中很好的得到体现
于是考虑在外部枚举，注意一些细节即可。