written on 2022-08-09
一道有趣的计数题。
首先题面中最引人注目的就是两个整数的数据范围。很显然，暴力的思路，枚举所有数，找出每一位上每一种数字的个数这种方法是不可行的。
现在我们来思考一下暴力解法的瓶颈。如果我们延续“找出每一位上每一种数字的个数”这种思路的话，就必须舍去枚举所有数的过程，用高效的方式求解。
先设 \(f_{x,i}\) 表示 \(L\) ~ \(R\) 区间内，第 \(x\) 位，数字为 \(i\) 的数的个数。一开始想到数位 \(\texttt{dp}\)，进而发现该数组显然是满足区间可减性的。所以考虑分开计算两部分，那么重点即在于计算 \(1\) ~ \(n\) 中每一位数字为 \(i\) 的个数。
一下可能没有什么直观的思路，所以可以模拟一下一些数据观察其特性。这里直接给出结论，当然在此之前强烈建议先自己尝试模拟一下。
对于第 \(x\) 位的数，若 \(n\) 在这一位上的数字是 \(s_i\)，那么对于这一位上的某一种待统计的数字 \(a\)：
-
若 \(a\lt s_i\)，则 \(cnt=(pre_{i-1}+1)\times 10^{len-i}\)。
-
若 \(a=s_i\)，则 \(cnt=pre_{i-1}\times 10^{len-i}+(suf_{i+1}+1)\)。
-
若 \(a\gt s_i\)，则 \(cnt=pre_{i-1}\times 10^{len-i}\)。
上述等式中，\(pre_i\) 表示首位至第 \(i\) 位的所有位的数字顺序排列构成的数，\(suf_i\) 表示第 \(i\) 位至末位的所有位的数字顺序排列构成的数。
剩下的就是最后统计答案了，求出 \(f\) 数组后暴力枚举每一位上的两个数，直接计算即可。
这题的关键在于发现 \(f\) 数组的区间可减性。另外，以后看到这种类似的统计数位个数的题就可以直接明确统计思路了，算是总结吧。
标签：pre,cnt,数字,COCI2013,个数,P8245,times,62,len From： https://www.cnblogs.com/Freshair-qprt/p/16585605.html