「HLOI2016」幸运数字

Posted on In
HLOI2016 Day2 T3

题目描述

小明是个非常喜欢幸运数字的同学，他认为自己的幸运数字是 。同时他非常喜欢偶数，所以他认为如果 出现在某一个整数的所有的左起（从 开始计数）偶数位上，那这个整数就是他的幸运数。

这天，小刚想要考小明一个问题，他说给小明一个区间 ，问这个区间里能够整除 的幸运数有多少个。

输入

输入的第一行是一个整数 ，第二行是两个整数 和 ，代表询问的区间。

输出

输出中仅包含一个数字，即对应输入文件的答案。由于答案可能比较多，输出答案应对 取余。

样例输入

1
2
3
10 99

样例输出

1
3

样例说明

到 之间有 可以整除 ，并且是幸运数字。

数据范围及约定

对于 的数据： ；

对于 的数据： 。

数据保证 和 的位数一致并没有前导零。

时间与空间限制

时间限制：，空间限制：。

题解

HLOI2016 全 AC 达成。

和 太大了，典型数位 DP 题。 于是这就成为本蒟蒻第一道数位 DP……

两个 DP 数组，用 表示 中，前 位组成的数余数为 ，且组成的数大于（ ），等于（ ）或小于（ ）左或右区间的数。

每次加入一位数，比前 位大的转移到比前 位大，小的同理。相等的可以自行意会……

初值就是把 扫一遍，加到 DP 数组里。

答案是 。具体转移和答案参见代码。

题解说了跟没说一样。

然后不知为何貌似数据错了？

省选题数据会错？

如果哪位神犇看出了错误请留言或发个邮件什么的。

平均来算，时间复杂度应该为 。 为数字位数。空间复杂度为 。

代码见这里。