P2602 [ZJOI2010] 数字计数
GUO120822
·
·
题解
非常好懂又简洁的题解，不压行只有 9 行！
思路来源：leomaster
数据范围很大，考虑数位dp小学奥数。
题目要求计算 0 到 9 的答案，直接枚举，对于每一个数计算。
下文记 f(n,x) 表示 n 以内，x 的答案。
由于是求 l 到 r 的答案，我们容斥一下，用 r 的答案减去 l 的答案。
对于每一位造成贡献，于是我们枚举 i。
$i$ 为 $10$，十位。
一直枚举到 $n$ 的最后一位。
来考虑每一位。
分两种情况讨论：
1. 前面填更小的，一共 $n/i/10$ 种可能，乘上后面随便填，这一位就是 $n/i/10*i$。
2. 前面填相同的，若这一位相同，那么后面只能填更小的 $0$ 到 $n$ 取余 $i$ 一共 $n$ 取余 $i$ 再加 $1$ 种可能。
3. 这一位更小，后面随便填，一共 $i$ 种可能。
```cpp
#include<stdio.h>
typedef long long ll;ll a,b,i;
inline ll f(ll n,ll x){
ll cnt=0,i;for (i=1;n/i;i*=10){
cnt+=n/i/10*i-(x==0)*i;
if (x<n%(i*10)/i) cnt+=i;
else if (x==n%(i*10)/i) cnt+=n%i+1;
}return cnt;
}int main(){scanf("%lld%lld",&a,&b);for (i=0;i<=9;i++) printf("%lld ",f(b,i)-f(a-1,i));}