P2602 [ZJOI2010] 数字计数

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=250,mod=998244353;
LL f[20][20];//长度为i时，前pos-1项的和为j的合法数
string s;

//pos位置，sum==mark目标，limit限制，isnum是否存在数字
LL dfs(int pos,LL sum,bool limit,bool isnum,int op){
  int up=limit?s[pos]-'0':9;//如果有限制那么最多只能枚举到该位置，否则会超出n的范围
  if(pos==(int)s.size()){//到达终点，注意要越过其长度
    return sum;
  }
  if(isnum&&!limit&&f[pos][sum]!=-1) return f[pos][sum];//记忆化
  LL res=0,add=0;
  //只有前面都为前导0才可以
  if(pos<(int)s.size()&&!isnum) res=dfs(pos+1,0,false,false,op);//跳过，注意边界
  for(int i=1-isnum;i<=up;i++){//范围，以及起始边界
 	//前面没有数字，且当前选了0，要记录0，add为0
 	if(i==0&&!isnum&&!op) add=0;
    else add= (i==op);//如果前面都是前导0，没有前面的限制会出错
    res+=dfs(pos+1,sum+add,i==up&&limit,true,op);//每一个位置的合法数都要枚举
  }
  //如果没有限制，那么pos位置可以随便填，会出错
  if(isnum&&!limit) f[pos][sum]=res;//如果存在数，且在合法范围内，记忆化
  return res;

}


LL work(LL n,int op){
  memset(f,-1,sizeof f);
  s=to_string(n);
  LL ans=dfs(0,0,true,false,op);
  return  ans;
}

int main()
{
  LL a,b;
  cin>>a>>b;
  for(int i=0;i<=9;i++){
     cout<<work(b,i)-work(a-1,i)<<' ';
  }

  return 0;
}