数位dp(记忆化搜索)
作者:
zsfzmxl
,
2024-03-16 11:22:19
,
所有人可见
,
阅读 56
#include<bits/stdc++.h>
using namespace std;
const int N=15;
long long dp[N][N];//最后i位前面2的个数为j时,数字2的总个数
int num[N],now;
/*
lead 是否有前导0
limit 如果当前最高位0~9,=false。否则true
pos 当前处理到第pos位
*/
long long dfs(int pos,int sum,bool lead,bool limit){
long long ans=0;
if(pos==0)return sum;
if(!lead&&!limit&&dp[pos][sum]!=-1)return dp[pos][sum];
int up=(limit?num[pos]:9);
for(int i=0;i<=up;i++){
if(i==0&&lead)ans+=dfs(pos-1,sum,true,limit&&(i==up));
else if (i==now)ans+=dfs(pos-1,sum+1,false,limit&&(i==up));
else if(i!=now)ans+=dfs(pos-1,sum,false,limit&&(i==up));
}
if(!lead&&!limit)dp[pos][sum]=ans;
return ans;
}
long long solve(long long x){
int len=0;
while(x){
num[++len]=x%10;
x/=10;
}
memset(dp,-1,sizeof dp);
return dfs(len,0,true,true);
}
int main(){
long long a,b;
cin>>a>>b;
for(int i=0;i<=9;i++){
now=i;
cout<<solve(b)-solve(a-1)<<" ";
}
return 0;
}