规范:
1、上界用up
2、前导0用 ld 且ld为0时表示有前导0,为1时没有
3、前3位为从左往右数三位
4、第3位为从右往左数
5、当前位p还没有填
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[17];
ll vis[17][17]; //vis是通解,不计入特解,所以vis在这里记忆化无前导零且非上界的后继方案数 //vis[i][j]表示i位前面有j个符合的数字,后面满足条件的个数
ll dfs(int p,bool up,ll sum,bool lead,int dig){ //分别表示位置、上界、前面符合条件的的数字数、前导0、统计的目标数字
if(p==0) return sum; //
if(up==0&&vis[p][sum]&&lead) return vis[p][sum];
int cnt=up?a[p]:9;
ll res=0;
for(int i=0;i<=cnt;++i){
//res+=dfs(p-1,up&&(i==a[p]),sum+(i==dig&&!(i==0&&lead)),lead&&i==0,dig);
res+=dfs(p-1,up&&(i==a[p]),sum+((i||lead)&&(i==dig)),lead||i,dig);
}
if(up==0&&lead) return vis[p][sum]=res; //无前导0,因为若有,则统计0时答案会错,因为00和09这两点统计0时的后继方案数不同
return res;
}
ll cal(ll x,int i){
int cnt=0;
while(x){
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,1,0,0,i);
}
ll l,r;
int main(){
cin >> l >> r;
for(int i=0;i<=9;++i){
cout << cal(r,i)-cal(l-1,i);
if(i!=9) cout << " ";
else cout << "\n";
memset(vis,0,sizeof vis);
}
return 0;
}

京公网安备 11010502036488号