关于一个求出 [0, x) 中某数位出现的次数的方法

blue_ice · 2022-07-23 13:19:57 · 个人记录

关于一个求出 [0, x) 中某数位出现的次数的新方法

（大佬先别说数位 DP，先听我讲）

如果我们要求出 [0, 114514) 中数位 7 出现的次数，我们可以把这个区间分成两段：[0, 114000),[114000,114514)。分别考虑怎么求出这两个区间中数位 7 出现的个数。

[0, 114000)

我们可以把 [0,114000) 里的所有数劈成两截：前三位和后三位（不足的在前面补零）。

先考虑前三位。每个“前三位”都在这个区间里出现了 1000 次，所以我们可以求出 [0,114) 中数位 7 出现的次数，然后再乘以 1000，就可以求出 [0,114000) 里每个数前三位所包含的 7 的个数。

考虑后三位。根据相似的逻辑，每个“后三位”都在 [0, 114000) 里出现了 114 次，所以我们可以求出 [0, 1000) 中数位 7 出现的次数，然后再乘以 114，就可以求出 [0,114000) 里每个数后三位所包含的 7 的个数。

最后把两个结果加起来，就得到了 [0,114000) 中数位 7 出现的次数。

[114000,114514)

同样的逻辑，我们依然可以把 [114000,114514) 里的所有数劈成两截：前三位和后三位。

根据主定理，这个算法的时间复杂度是 O(n^{\log_2(3)})。

应用

有人可能会说：你讲了那么长时间，这算法的时间复杂度还是不如数位 DP 啊，有什么用呢？其实这个可以用在多次查询上面……

如果我们想多次查询 [0,m) 中数位 7（仍然是举例子）的个数，给出条件 1\le m \le n，这个算法可以做到 O(\sqrt n\log n) 预处理，O(1) 查询。下面我来解释这一点。

首先，预处理出每个在 [1,10\sqrt n] 里的数里面分别有多少个 7。

然后，对于每一次询问（[0, m)），我们用上面的流程把它分成 4 个子问题，可以注意到，这四个子问题的答案都已经在上面被预处理过了（如果想要求出某个数 k 有多少个 7，可以直接用 [0, k+1) 中数位 7 出现的次数减去 [0, k) 中数位 7 出现的次数），所以就可以用 O(1) 的时间得出结果。

现在证明预处理的复杂度。对于任意一个 k，可以用 O(\log k) 的时间复杂度求出 k 里面有多少个 7，再把这个和之前算出来的 [0, k) 中数位 7 出现的次数加起来，就可以得到 [0, k+1) 中数位 7 出现的次数了。

由于这个操作要执行 10\sqrt n 次，每次最多需要 O(\log n) 的时间，所以总的时间复杂度就是 O(\sqrt n\log n)。

如果各位大佬们看见哪个地方有问题或者没讲明白，可以告诉我。如果您在网上看见了相似的资料，也可以告诉我。

习题
代码

优化

注意到在求的过程中，有一步肯定是求 [0,10^x) 中有多少数位 7（在上面的例子中 x=3），所以我们可以先预处理一下这些情况。

这样又引出了一个问题：如何快速求出 [0,10^x) 中有多少数位 7 呢？

我们可以分别考虑每一位，看看每一位中有多少数位 7。

由于我们看的是有多少数位 7，所以我们可以把 7 固定在这个数位上，其他的数位上随便选，所以每个数位上都有 10^{x-1} 个数位 7，一共有 x 个数位，所以整个区间就有 x\cdot 10^{x-1} 个数位 7。

我们可以先预处理出能用到的 10 的幂（所有能用到的幂肯定在 [1,10^{\lceil\frac{n}{2}\rceil}] 之间），这样我们就可以用 O(n) 的时间预处理所有 1\le x\le\lceil\frac{n}{2}\rceil 的情况，在算 [0,10^x) 中有多少数位 7 的时候只需要 O(1) 查找预处理的结果就行了。

优化版的算法的递推关系式：T(n)=\begin{cases}O(1) & n=1\\2T\left( \frac{n}{2}\right)+O(n) & n>1\end{cases}

根据主定理，这个算法的时间复杂度是 O(n\log n)。

拓展

如果想要查询 [0, x) 中数位 0 出现的次数，上面的方法就需要改一改了。（因为有前导 0)

这次还是拿 [0,114514) 来举例子。如果我们要求出 [0,114514) 中数位 0 出现的次数，这次我们要把它分成三个区间：[0,1000)，[1000,114000)，[114000,114514)。

[0,1000)

我们把这部分变成 0+(0,1000]-1000。先考虑 (0,1000] 这部分仍然可以找规律。仍然按位分，注意到有 100 个数最后 1 位是 0 ，有 10 个数最后 2 位是 0，有 1 个数最后 3 位是 0，一共 100+10+1=111 个 0。
加上 0 的 1 个 0，再减去 1000 的 3 个 0，就得到了最终的答案：109。
这部分是有规律的，所以可以预处理一下。

[1000,114000)

分成前三位和后三位。求出 [1,114) 中有多少数位 0（可以看成 [0,114)-0），然后乘上 1000，就可以得到前三位中数位 0 的个数。再求出 [0,1000) 里面数位 0 的个数（含前导 0，可以用前面求 7 的思路求，注意传位数进去，也可以用规律求），乘上 113，就可以得到后三位中数位 0 的个数。把两个结果加起来，就可以得到这个区间中数位 0 的个数。

[114000,114514)

再次分成前三位和后三位。求出 114 中有多少数位 0，再乘以 514，就得到前三位中数位 0 的个数。求出 [0, 514) 中有多少 0（含前导 0，还是用之前的思路求，记得传位数），再把两个结果加起来，就可以得到这个区间中数位 0 出现的个数了。

最后把三个区间的和加起来即可。

注意到，我们把原问题分成了 2 个子问题：[0,114) 中数位 0 的个数（不含前导 0），[0,514) 中数位 0 的个数（含前导 0）。

递推关系式：T(n)=\begin{cases}O(1) & n=1\\T\left(\frac{n}{2}\right)+O(n\log n) & n>1\end{cases}

根据主定理，这个算法的时间复杂度是 O(n\log n)。

（PS：这个也可以按照前面的思路应用）