1833: [ZJOI2010]count 数字计数
题目：传送门
题解：
今天是躲不开各种恶心DP了？？？
%爆靖大佬啊！！！
据说是数位DP裸题...emmm学吧学吧
感觉记忆化搜索特别强：
定义f[i][j][k]表示若前i个位置有k个j的此时的全局方案数，然后就可以记忆化搜索了（具体看代码吧）
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL f[][][],a[];
LL n,m;
LL dfs(int pos,int x,int sum,bool ld,bool lt)//ld表示当前情况是否要考虑前导0，lt表示的是枚举数字的上限是否有规定
{
if(pos==)return sum;
if(ld==false && lt==false && f[pos][x][sum]!=-)return f[pos][x][sum];
LL up=,ans=;if(lt==true)up=a[pos];
for(int i=;i<=up;i++)
{
int ss=sum;bool bk1=false,bk2=false;
if(i==x)ss++;
if(ld==true && i==){bk1=true;if(x==)ss--;}
if(lt==true && i==a[pos])bk2=true;
ans+=dfs(pos-,x,ss,bk1,bk2);
}
if(ld==false && lt==false)f[pos][x][sum]=ans;
return ans;
}
LL sol(LL x,int y)
{
int pos=;
while(x){a[++pos]=x%;x/=;}
return dfs(pos,y,,,);
}
int main()
{
memset(f,-,sizeof(f));
scanf("%lld%lld",&n,&m);
for(int i=;i<;i++)printf("%lld ",sol(m,i)-sol(n-,i));
printf("%lld\n",sol(m,)-sol(n-,));
return ;
}