自动搬运

查看原文

来自洛谷，原作者为

	ybe2007 适度OI益脑，沉迷OI伤身

搬运于2025-08-24 22:37:15，当前版本为作者最后更新于2022-08-09 10:27:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道有趣的计数题。

首先题面中最引人注目的就是两个整数的数据范围。很显然，暴力的思路，枚举所有数，找出每一位上每一种数字的个数这种方法是不可行的。

现在我们来思考一下暴力解法的瓶颈。如果我们延续“找出每一位上每一种数字的个数”这种思路的话，就必须舍去枚举所有数的过程，用高效的方式求解。

先设 $f_{x,i}$ 表示 $L$ ~ $R$ 区间内，第 $x$ 位，数字为 $i$ 的数的个数。一开始想到数位 $\texttt{dp}$，进而发现该数组显然是满足区间可减性的。所以考虑分开计算两部分，那么重点即在于计算 $1$ ~ $n$ 中每一位数字为 $i$ 的个数。

一下可能没有什么直观的思路，所以可以模拟一下一些数据观察其特性。这里直接给出结论，当然在此之前强烈建议先自己尝试模拟一下。

对于第 $x$ 位的数，若 $n$ 在这一位上的数字是 $s_i$，那么对于这一位上的某一种待统计的数字 $a$：

1. 若 $a\lt s_i$，则 $cnt=(pre_{i-1}+1)\times 10^{len-i}$。

2. 若 $a=s_i$，则 $cnt=pre_{i-1}\times 10^{len-i}+(suf_{i+1}+1)$。

3. 若 $a\gt s_i$，则 $cnt=pre_{i-1}\times 10^{len-i}$。

上述等式中，$pre_i$ 表示首位至第 $i$ 位的所有位的数字顺序排列构成的数，$suf_i$ 表示第 $i$ 位至末位的所有位的数字顺序排列构成的数。

剩下的就是最后统计答案了，求出 $f$ 数组后暴力枚举每一位上的两个数，直接计算即可。

这题的关键在于发现 $f$ 数组的区间可减性。另外，以后看到这种类似的统计数位个数的题就可以直接明确统计思路了，算是总结吧。