[数据结构与算法]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;
}