[ZJOI2010]数字计数 解题思路

数字计数

题目大意

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码（$0,1,2,…,8,9$）各出现了多少次。

思路

其实就是算从 $0$ 到 $n$ 中，每个数出现的次数，再用前缀和的方式去计算区间 $[a,b]$。那么重点就是去计算每个数的出现次数。

Step1

我们用 $dp[i]$ 表示 $0$ 到有 $i$ 个 $9$ 的数中，每个数码的出现个数（考虑前导 $0$），比如 $i=3$，$dp[i]$ 表示的就是 $0$ 到 $999999999$ 中，每个数的出现次数。

显然 $dp[1] = 1$（$0 \sim 9$ 每个数都出现了一次）。

对于 $i \ge 2$：

• 对于一个 $i$ 位数，我们先考虑 $[1, i-1]$ 位的贡献，因为第 $i$ 位数可以选择 $0 \sim 9$ 中任意一个数，相当于多了 $10$ 种方案，所以 $dp[i] += 10 \cdot dp[i-1]$。
• 我们再考虑第 $i$ 位数的贡献，对于每个数码 $x \in [0, 9]$，后面 $i-1$ 位都可以任意选择，构成一个 $i$ 位数，故有 $10^{i-1}$ 种选择，所以 $dp[i] = 10 \cdot dp[i-1] + 10^{i-1}$。

我们就轻而易举地得到了 $dp$ 的递推式。

Step2

那么第二步就是用这个 $dp$ 式去推结果。我们先举一个例子，比如 $7432$ 这个数。

我们来尝试去构造每个在 $[0, 7432]$ 之间的数，依次作为媒介来计算。

• 如果我们在第四位上选择了 $[0, 6]$ 之间的数，那么剩下的三位数就可以任选了，那么剩下的三位数的贡献就是 $7 \cdot dp[3]$。
• 假如我们选择了 $7$ 这个数，那么剩下的数就不能任选了，最多选到 $432$ 这个数，在此条件上，我们来计算第四位数的贡献：如果选择 $[0, 6]$ 中数码，那么后面每一位上的数都可以任选，显然就有 $10^2$ 种；而选择了 $7$，那么后面三位最多选到 $432$，所以有 $433$ 种（因为可以全部选 $0$）。
• 此时 $4$ 位数已经计算过了，那么就是要计算三位数，就变成了求 $[0, 432]$ 之间的数了，所以重复上述过程即可。
• 处理前导 $0$：四位数时，含有前导 $0$ 的数是 $[0000, 0999]$，共有 $10^3$ 种；三位数时，有 $[000, 099]$，共有 $10^2$ 种，以此类推……

那么具体地到一般情况，假设我们计算 $[0, n]$ 中，每个数码的出现数量。设 $ans[i]$ 表示数码 $i$ 的出现数量。我们从 $n$ 的最高位（设之为 $cnt$ 位）开始算，设它的第 $i$ 位为 $a[i]$。

对于每一位 $a[i]$（与上述例子类似）：

• 计算第 $[1, i-1]$ 位数的贡献：第 $i$ 位可选 $[0, a[i]]$，剩下位数任选，所以 $\forall j \in [0, 9]$，$ans[j] += a[i] \cdot dp[i-1]$。
• 计算第 $i$ 位数对答案的贡献：当第 $i$ 位选择 $[0, a[i]-1]$ 之间的数时，后面所有数位都可以任选，答案可以直接计算，即 $\forall j \in [0, a[i]-1]$，$ans[j] += 10^{i-1}$；当第 $i$ 位选择 $a[i]$ 时，后面的数只能从 $0$ 选到后面几位构成的数，设之为 $tmp$，那么 $ans[a[i]] += tmp + 1$。

代码

#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 1005;

long long l, r, dp[maxN], mi[maxN], ans1[maxN], ans2[maxN], a[maxN];

void solve(long long n, long long *ans)
{
    long long tmp = n;
    int cnt = 0;
    while(tmp) {
        a[++cnt] = tmp % 10;
        tmp /= 10;
    }
    for(int i = cnt; i >= 1; --i) {
        for(int j = 0; j <= 9; ++j)
            ans[j] += a[i] * dp[i - 1];
        for(int j = 0; j < a[i]; ++j)
            ans[j] += mi[i - 1];
        n -= mi[i - 1] * a[i];
        ans[a[i]] += n + 1;
        ans[0] -= mi[i - 1];
    }
}

int main()
{
    scanf("%lld%lld", &l, &r);
    mi[0] = 1;
    for(int i = 1; i <= 13; ++i) {
        dp[i] = 10LL * dp[i - 1] + mi[i - 1];
        mi[i] = mi[i - 1] * 10LL;
    }
    solve(r, ans1);
    solve(l - 1, ans2);
    for(int i = 0; i <= 9; ++i)
        printf("%lld ", ans1[i] - ans2[i]);
    return 0;
}