巨大的数（dp+矩阵加速）

第3题     巨大的数 查看测评数据信息

小明定义了一种生成大数的函数f[n],他的含义是将1-n所有的正整数按照从小到大拼接起来，形成一个巨大的数，例如f[13]=12345678910111213,现在给定一个数n，输出f[n]%m的值，其中n和m都是正整数

输入格式

第一行两个整数n,m

部分数据：1<=n<=1e6

全部数据：1<=n<=1e18,1<=m<=1e9

输出格式

一个整数

输入/输出例子1

输入：

13 13

输出：

4

样例解释

无

先考虑朴素dp

f(i): 前i个数拼起来，%m是多少
由f(i-1)转移

举个例分析下

假设有一串数，以i-1结尾，且f[i-1]=x，可以这样表示：

(1234567...i-1)%m=x
令y=(1234567...i-1)
在这一串数后面加i，相当于变成：

(y*10^k+i)%m
=(y%m * 10^k%m + i)%m

那么转移方程就出来了

k: i有多少位
f(i) = ((f(i-1) * 10^k) %m + i) %m

然后我们算出矩阵

已知量肯定是f(i-1)，i，由于有个10^k，我们还要补个1才能计算

[f(i-1), i, 1] * [A] = [f(i), i+1, 1]

[A]:

[10^k, 0, 0]
[1, 1, 0]
[0, 1, 1]

答案不就是[f(i-1), i, 1]*[A]^(i-1)吗

但是k会变化！

所以考虑分段处理，分19段

k的长度：对应的值
1 ：0~9
2 ：10~99
3 ：100~999
4 ：1000~9999
............
18 : 10^17~10^18-1
19 : 10^18

那么我们分别求出k的长度以及其对应的值，再改变一下矩阵，不就可以套算答案的那个公式了吗？

具体地，我们要对n进行分段，分成k段，每段长度是i

为了方便，我们k从1开始（也可以从0开始，但是改变矩阵的时改变它的那个值要+1）

k的长度枚举范围应该是1~n的长度

那么就要考虑如何算出k所对应的这个区间里面的数有多少个了。例如k=3，对应的区间的数个数就是  999-100+1=900

我们可以算出k对应的下限值。例如k=2，它对应的下限值是10，也就是  10^(k-1)+1，上限值是99，也是可以确定的，也就是10^k-1，那不就可以算了吗

但是有个细节，我们得分类讨论

1.现在循环的时候，n远远大于k所对应的区间的最大值，也就是n>k对应的区间的上限值，我们就可以直接算。例如n=1002，k=3，那么k对应的值的范围是100~999，我们可以直接用k对应的区间的上限减去下限（999-100+1）

那么一般情况：n>10^k，上限值-下限值，也就是  10^k-1-(10^(k-1)+1)+1

2.现在循环的时候，n就再k所对应的区间之间，也就是n<k对应的区间的上限值，不就把上限值给调整下吗。