数位统计前缀差：cnt(n,d) 逐位拆 high/cur/low 计算每位贡献，0 需扣掉前导零情形，答案作 cnt(b)-cnt(a-1)。
OJ: roj
题目 ID: 3180
难度:普及
标签:数位DP递推
创建: 2026-10-01 23:31
更新: 2026-10-06 11:58
题目描述
给定整数 0 0 结束（该行不处理），每组输出十个空格隔开的整数，依次为
样例输入：1 10、0 0；样例输出：1 2 1 1 1 1 1 1 1 1。
思路
答案作前缀差
参考代码
Python 版：
python
"""数位统计 DP：cnt(n, d) 统计 1..n 中数字 d 的出现次数，答案作前缀差。"""
import sys
def cnt(n: int, d: int) -> int:
"""统计 1..n 中数字 d 出现的总次数，逐位贡献法 O(log n)。"""
res, p = 0, 1 # p 为当前统计的位权（个位、十位、……）
while p <= n:
high, cur, low = n // (p * 10), n // p % 10, n % p # 高位 / 当前位 / 低位
if d == 0:
# 0 不能作前导：前缀（高位部分）必须 >= 1
if high:
res += (high - 1) * p + (p if cur else low + 1)
else:
# 前缀取 0..high-1 时低位任意；前缀等于 high 时按当前位与 d 比大小
res += high * p + (p if cur > d else low + 1 if cur == d else 0)
p *= 10
return res
for line in sys.stdin:
a, b = map(int, line.split())
if a == b == 0: # 终止行不处理
break
if a > b:
a, b = b, a # a 可能大于 b，先交换
print(*[cnt(b, d) - cnt(a - 1, d) for d in range(10)])C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 11:58
* update_at: 2026-10-06 11:58
*/
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
// cnt(n, d)：统计 1~n 的十进制写法中数字 d 出现的总次数（逐位算贡献）。
ll cnt(ll n, ll d) {
ll res = 0;
for (ll p = 1; p <= n; p *= 10) {
ll high = n / (p * 10); // 高位部分：第 p 位左边的数
ll cur = n / p % 10; // 当前第 p 位上的数字
ll low = n % p; // 低位部分：第 p 位右边的数
if (d == 0) {
// 0 不能作前导零，高位部分必须至少为 1
if (high >= 1) {
res += (high - 1) * p; // 高位取 1~high-1，低位任取
if (cur == 0) {
res += low + 1; // 高位恰好等于 high，低位只能取 0~low
} else {
res += p; // 当前位本来就是 0，低位任取
}
}
} else {
res += high * p; // 高位取 0~high-1，低位任取
if (cur > d) {
res += p;
} else if (cur == d) {
res += low + 1;
}
}
}
return res;
}
int main() {
ll a, b;
while (cin >> a >> b && (a != 0 || b != 0)) {
if (a > b) {
swap(a, b); // 题面中 a 可能大于 b
}
for (ll d = 0; d <= 9; d++) {
if (d > 0) {
cout << ' ';
}
cout << cnt(b, d) - cnt(a - 1, d); // 前缀差求区间内出现次数
}
cout << '\n';
}
return 0;
}