数位DP 数位和
作者:
林小胖
,
2022-03-05 10:18:36
,
所有人可见
,
阅读 225
const int N=2e5+10,M=5e5+10;
int a[N];
ll l,r;
ll ans[N],f[N];
// 计算0—9在区间[1,n]中出现的次数
void calc(ll n,int tmp){//tmp:1表示加 -1表示减
// 存入数组
int t=0;
for(;n;n/=10)a[++t]=n%10;
reverse(a+1,a+t+1);
//枚举第i类
for(int i=1;i<=t;i++){
//处理 <i 的位置 j 的贡献
for(int j=1;j<i;j++)ans[a[j]]+=tmp*a[i]*f[t-i];
// 考虑第 i 位的贡献
// 非零的的数字
for(int j=1;j<a[i];j++)ans[j]+=tmp*f[t-i];
// 当前不是第一类并且当前这一位可以放0
if(i!=1&&a[i])ans[0]+=tmp*f[t-i];
if(t!=i){
// 考虑 >i 的那些位置的贡献
// 非零的的数字
for(int j=1;j<10;j++)ans[j]+=tmp*f[t-i-1]*(t-i)*a[i];
// 当前不是第一类并且当前这一位可以放0
if(i!=1)ans[0]+=tmp*f[t-i-1]*(t-i)*a[i];
}
// 统计第一类中 0 出现的次数
if(i==1){
// 考虑首位非0
if(t>=2)ans[0]+=tmp*(a[1]-1)*(t-1)*f[t-2];
// 考虑后面那些位置非 0
for(int j=2;j<t;j++)ans[0]+=tmp*9*(t-j)*f[t-j-1];
}
}
// 统计 n 的贡献
for(int i=1;i<=t;i++)ans[a[i]]+=tmp;
}
int main(){
// f[i]=10的i次方
for(int i=1;i<=16;i++)f[i]=f[i-1]*10;
cin>>l>>r;
calc(r,1);
calc(l-1,-1);
for(int i=0;i<10;i++)cout<<ans[i]<<" ";
cout<<endl;
return 0;
}