数字计数题两种解法对比
暴力极致常数优化 + 数学推导O(LOGN)通杀大数据
本题解制作不易，可以点点赞吗？Thanks♪(･ω･)ﾉ
一、题目简述
题意
给定 M,NM,NM,N，统计区间 [M,N][M,N][M,N] 内数字0~9各自出现次数。
数据范围
1≤M≤N≤2×1091\le M\le N\le 2\times 10^91≤M≤N≤2×109，N−M≤5×105N-M\le 5\times 10^5N−M≤5×105
样例
输入：129 137
输出：1 10 2 9 1 1 1 1 0 1
二、题意分析数据范围关键点
1. 区间长度最大 5×1055\times 10^55×105：暴力拆解每位数字可过，只需极致常数优化；
2. 若题目取消区间限制、仅给 1≤M≤N≤10181\le M\le N\le 10^{18}1≤M≤N≤1018，暴力必TLE，必须数位统计；
3. 原暴力代码存在两个致命问题：
* while(x) 无法统计数字0；
* cin/cout IO过慢，大数据容易TLE；
* 循环变量int存不下大数，存在溢出风险。
三、方案1：原题暴力极致常数优化（不改核心遍历逻辑）
完全保留「遍历每个数→逐位拆分统计」原始逻辑，仅做IO、循环、分支常数优化，适配本题给定区间限制。
优化点说明（完全不改动统计逻辑）
1. 移除万能头，仅引入<cstdio>，减少程序加载内存，规避glibc额外开销；
2. cin/cout 替换为scanf/printf，关闭同步开销，IO速度提升数倍；
3. while(x) 改为do-while：天然兼容数字0，省去单独判断if(!x)分支，减少判断耗时；
4. 循环变量统一ll，避免大数区间溢出；
5. 无全局数组，vis存栈，内存占用恒定极小，不会MLE；
6. 前置++i替代后置i++，减少临时变量拷贝常数开销。
适用场景
本题限定 N−M≤5×105N-M\le 5\times 10^5N−M≤5×105，此代码速度足够，代码简短易写，适合赛时快速敲出。
四、方案2：数学推导通用解法（通杀所有超大区间）
数位计数数学完整推导（求 1∼X1\SIM X1∼X 数码 *** 出现次数）
设数字按位拆分：
X=high cur low‾X = \overline{high\ cur\ low} X=high cur low
* p=10kp=10^kp=10k：当前位权（第 kkk 位）
* cur=⌊Xp⌋ mod 10cur = \left\lfloor \frac{X}{p} \right\rfloor \bmod 10cur=⌊pX ⌋mod10：当前位数字
* high=⌊X10p⌋high = \left\lfloor \frac{X}{10p} \right\rfloorhigh=⌊10pX ⌋：高位整体
* low=X mod plow = X \bmod plow=Xmodp：低位整体
分两类：D≠0D\NEQ 0D=0、D=0D=0D=0（0不能做前导，公式不同）
1、D≠0D \NEQ 0D=0
1. d<curd < curd<cur
高位可取 0∼high0\sim high0∼high，低位任意 0∼p−10\sim p-10∼p−1
ans+=(high+1)×pans += (high+1)\times p ans+=(high+1)×p
2. d=curd = curd=cur
高位 0∼high−10\sim high-10∼high−1 完整一组 + 高位=highhighhigh 时低位 0∼low0\sim low0∼low
ans+=high×p+(low+1)ans += high\times p + (low+1) ans+=high×p+(low+1)
3. d>curd > curd>cur
高位仅 0∼high−10\sim high-10∼high−1
ans+=high×pans += high\times p ans+=high×p
2、D=0D = 0D=0（最高位不能为0，高位从 111 开始）
1. 0<cur0 < cur0<cur
高位可取 1∼high1\sim high1∼high
ans+=high×pans += high\times p ans+=high×p
2. 0=cur0 = cur0=cur
高位 1∼high−11\sim high-11∼high−1 完整一组 + 高位=highhighhigh 低位 0∼low0\sim low0∼low
ans+=(high−1)×p+(low+1)ans += (high-1)\times p + (low+1) ans+=(high−1)×p+(low+1)
3. 0>cur0 > cur0>cur 不可能，无贡献
ans+=(high−1)×pans += (high-1)\times p ans+=(high−1)×p
3、区间答案公式
[L,R][L,R][L,R] 中数码 *** 出现次数：
f(R,d)−f(L−1,d)f(R,d) - f(L-1,d) f(R,d)−f(L−1,d)
f(x,d)f(x,d)f(x,d) 代表 1∼x1\sim x1∼x 数码 *** 总次数。
4、纯数学推导实现AC代码
5、样例代入验算：输入 129 137
计算 get(137,d)−get(128,d)get(137,d)-get(128,d)get(137,d)−get(128,d)，输出严格匹配样例：
1 10 2 9 1 1 1 1 0 1
6、复杂度证明
每轮循环 ppp 乘10，循环次数等于数字位数 log10X\log\\_{10}Xlog10 X，单次循环固定10个数字遍历，总时间 O(logX)O(\log X)O(logX)；
仅常数变量，空间 O(1)O(1)O(1)，极致时空。
五、两种方案取舍实战建议
1. 赛时快速过题、题目限制区间长度：直接用优化暴力，代码短、思考成本低；
2. 题目无区间上限、N−MN-MN−M可达101210^{12}1012：必须用数位统计，暴力直接TLE；
3. 内存严苛1MB限制场景：两种代码均无大数组、无STL容器，裸编译-nostdlib均可进一步压内存防MLE。
四、样例测试验证
输入：129 137
两段代码输出统一为：1 10 2 9 1 1 1 1 0 1，统计结果完全正确。
五、总结
1. 暴力优化版是针对本题数据范围的最优手写速敲代码，逻辑贴合初学者原始思路，仅做常数优化；
2. 数位统计是通用万能解法，复杂度碾压暴力，适合所有数位计数类拓展题；
3. 两种代码均无冗余代码、低内存占用，适配ACGO巅峰赛各类阴间内存、时间限制测试点。
六、方案2成果展示
这个方案时间O(logX)O(\log X)O(logX),空间O(1)O(1)O(1)，达到完美代码
图片为证：
本蒟蒻也是通过这道题，获得了“时空双修”
(*^▽^*)
