题解 LuoguP2602 [ZJOI2010]数字计数

发表于 分类于 阅读次数： Valine： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目传送门

题意：给定两个正整数 aa 和 bb ，求在 [a,b][a,b] 中的所有整数中，每个数码各出现了多少次。

数据范围：a≤b≤1012a\le b\le 10^{12}

首先，这道题显然是数位 DP 的套路题（统计某个区间内满足某个性质的数有多少之类的题基本都是数位DP）。

设状态 f[i][sum]f[i][sum] 表示已经考虑到了前 ii 位，目前的某个数码 dd 的个数为 sumsum 。

我们可以转移：f[i][sum]=∑f[i−1][sum−(now==d)]f[i][sum]=\sum f[i-1][sum-(now==d)] ，其中 nownow 表示考虑的第 ii 位上的数码。

采用记忆化搜索进行转移处理数位 DP 是很方便的，具体实现见代码（有注释）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int a,b;
int f[15][15][2][2];
int tot=0,num[15];
int dp(int x,int sum,int d,bool lim,bool zer) {
    /*
    x表示当前到了第几位，sum表示当前答案，d表示需要处理个数的数码，
    lim表示是否在上界，zer表示是否为前导0。
    */
    if(x==0) return sum;
    //递归到终点了，返回答案
    if(~f[x][sum][lim][zer]) return f[x][sum][lim][zer];
    //给f数组加入了lim和zer两个0/1量来保证返回的数据是符合当前条件的。
    int ans=0;
    rep(i,0,lim?num[x]:9) {
        //这里判断lim是为了处理在上界时只能for到b的那一位的情况。
        if(zer&&i==0) ans+=dp(x-1,sum,d,0,1); //前导的0不计入答案。
        else ans+=dp(x-1,sum+(i==d),d,lim&&(i==num[x]),0);
    }
    return f[x][sum][lim][zer]=ans; //赋值用于记忆化。
}
int sol(int d,int x) {
    memset(f,-1,sizeof(f));
    tot=0;
    while(x) num[++tot]=x%10,x/=10; //拆位。
    return dp(tot,0,d,1,1);
}
signed main(){
    scanf("%llu%llu",&a,&b);
    rep(i,0,9) printf("%llu ",sol(i,b)-sol(i,a-1));
    return 0;
}