描述

给定一个区间$[a,b][a,b]$，为在这个区间当中[0,9]每个数字出现在各个数位上的次数

思路

• 数位dp模板题目，设$dp[i][j][k]dp[i][j][k]$表示考虑到第$ii$位，要计算的数是$jj$，并且$jj$之前出现了$kk$次的方案数，采用记忆化搜索的方式进行dp
• 采用dfs进行数位dp，具体的转移方法比较晦涩，可以参考代码注释

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[15][10][15];
int num[15];

ll dfs(int now,bool e,bool first,int target,int t)
/*
	now表示当前的数位
    e表示是否贴上界
    first表示是否为第1个数位
    target表示计算的值
    t表示之前出现了几次target
*/
{
    if(now==-1)
        return t;//如果数位考虑完，返回出现的次数
    if((!e)&&(!first)&&f[now][target][t]!=-1)
        return f[now][target][t];//记忆化搜索
    int u=e?num[now]:9;//计算当前可以遍历的最大的数
    ll res=0;
    if(first)//如果是第一个数且当前数位不填的情况
        res+=dfs(now-1,false,true,target,t);
    for(int i=first?1:0;i<=u;i++)//第一个数填写的情况
        res+=dfs(now-1,(i==u)&e,false,target,t+(i==target));
    return (e|first)?res:f[now][target][t]=res;//当不贴上界且不是第一个数的时候，将结果更新到记忆化数组当中
}

ll get(ll x,int target)
{
    int now=0;
    while(x)
    {
        num[now++]=x%10;
        x/=10;
    }
    return dfs(now-1,true,true,target,0);
}

int main()
{
    memset(f,-1,sizeof(f));
    ll a,b;
    scanf("%lld%lld",&a,&b);
    for(int i=0;i<=9;i++)
    {
        printf("%lld ",get(b,i)-get(a-1,i));
    }
    puts("");
}

时间复杂度$O(lo{g}_{10}(n))O(log\_\{10\}(n))$,空间复杂度$O(lo{g}_{10}(n))O(log\_\{10\}(n))$