「HLOI2016」幸运数字

Posted on In
HLOI2016 Day2 T3

题目描述

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

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

输入

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

输出

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

样例输入

1
2
3
10 99

样例输出

1
3

样例说明

10 到 99 之间有 27, 57, 87 可以整除 3，并且是幸运数字。

数据范围及约定

对于 30% 的数据：1 ≤ l < r ≤ 106；

对于 100% 的数据：1 ≤ m ≤ 2 × 103, 1 ≤ l < r ≤ 102 × 103。

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

时间与空间限制

时间限制：1000ms，空间限制：128MB。

题解

HLOI2016 全 AC 达成。

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

两个 DP 数组，用 f(i,j,k) 表示 [1,f] 中，前 i 位组成的数余数为 j，且组成的数大于（k = 0），等于（k = 1）或小于（k = 2）左或右区间的数。

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

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

答案是 R(n,0,2) + R(n,0,1) − L(n,0,2)。具体转移和答案参见代码。

题解说了跟没说一样。

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

省选题数据会错？

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

平均来算，时间复杂度应该为 。n 为数字位数。空间复杂度为 𝒪(nm)。

代码见这里。