SP3928 MDIGITS - Counting Digits 题解

题目：https://www.luogu.com.cn/problem/SP3928

一道经典的数位 DP，这里用记忆化搜索实现。

$f(i,j)$ 表示当前位数为 $i$，当前数码个数为 $j$ 时的状态。

从高到低枚举每一位，考虑每一位都可以填哪些数字。

如果当前位正好是要查询的数码，$sum$ 就加一。

还要考虑有前导零的情况，所以要加上一个判断前导零的参数 $lead$。如果有前导零，且当前数码正好为 0，$sum$ 不变，然后接着扫下去。即 sum+(((!lead)||i)&&(i==digit))。

剩下的就是套数位 DP 的模板了：

AC code：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[20],f[20][20000],l,r;
long long dfs(int pos,int digit,long long sum,bool lead,bool limit){
    //pos:当前数位; digit:要找的数码; sum:要找的数码的总和; lead:判断前导零; limit:判断限制位 if(pos==0) return sum;if(!limit&&!lead&&f[pos][sum]!=-1) return f[pos][sum];int up=limit?a[pos]:9; long long ans=0; for(int i=0;i<=up;i++)ans+=dfs(pos-1,digit,sum+(((!lead)||i)&&(i==digit)),lead&&!i,limit&&(i==up));  if(!limit&&!lead) f[pos][sum]=ans; return ans; 
}
long long handle(long long num,int digit){
    int pos=0;while(num)a[++pos]=num%10,num/=10;return dfs(pos,digit,0,1,1);
}
signed main(){
    memset(f,-1,sizeof(f));while(scanf("%lld %lld",&l,&r)==2&&l&&r){
    if(r<l) swap(l,r); //注意：r有可能小于l for(int i=0;i<=9;i++)cout<<handle(r,i)-handle(l-1,i)<<" ";puts("");}return 0;
}