题目地址：洛谷：【P2602】[ZJOI2010]数字计数 – 洛谷、BZOJ：Problem 1833. — [ZJOI2010]count 数字计数

题目描述

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输入输出格式

输入格式：
输入文件中仅包含一行两个整数a、b，含义如上所述。

输出格式：
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

输入输出样例

输入样例#1：

1 99

输出样例#1：

9 20 20 20 20 20 20 20 20 20

说明

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

题解

很传统的一个数位DP。
我们考虑从高位到低位DFS枚举每一位处理某个数码的出现次数，这个过程中需要特判上界以及特判前导0，这两个特判我们设置成flag加入DFS的状态中，分开处理就好了。DFS加个记忆化，然后跑的飞快。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 15;

LL a, b, num[MAXN], dp[MAXN][MAXN][2][2];

inline LL dfs(int len, int cnt, int digit, bool lim, bool zero) {
    if(dp[len][cnt][lim][zero] != -1) return dp[len][cnt][lim][zero];
    if(!len) return dp[len][cnt][lim][zero] = cnt;
    LL res = 0;
    for(int i = 0; i <= 9; i++) {
        if(lim && i > num[len]) break;
        res += dfs(len - 1, cnt + ((!zero || i) && i == digit), digit, 
            lim && i == num[len], zero && i == 0);
    }
    return dp[len][cnt][lim][zero] = res;
}

inline LL work(LL lim, int digit) {
    int len = 0;
    while(lim) {
        num[++len] = lim % 10; lim /= 10;
    }
    memset(dp, -1, sizeof(dp));
    return dfs(len, 0, digit, true, true);
}

int main() {
    a = readint(); b = readint();
    for(int i = 0; i <= 9; i++) {
        printf("%lld ", work(b, i) - work(a - 1, i));
    }
    return 0;
}