规范:
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; }