数位DP的使用条件

一道例题

给定两个正整数 $𝑎$ 和 $𝑏$ ，求在 $[a,b]$ 中的所有整数中，每个数码（digit）各出现了多少次。例如， $a=10$ ， $b=12$ ，则在区间 $[10,11,12]$ 中，数码 $0$ 出现了 $1$ 次，数码 $1$ 出现了 $4$ 次，数码 $2$ 出现了 $1$ 次。

输入：两个正整数 $𝑎$ 和 $𝑏$ ， $(1 \leq a \leq b \leq 10^{12})$ 。输出： $10$ 个整数，分别表示数码 $0$ 到 $9$ 在区间 $[a,b]$ 中出现的次数。

题解

这题很难。关键在于求出[0, b]中每个数码出现的次数，然后再减去[0, a-1]中每个数码出现的次数即可。

首先需要求dp数组，用于表示每位数码出现的次数。

定义状态

显然，00…0到99…9，每个数出现的次数都是相同的。例如，00到99中，每个数码出现19次（对于0：10~~90、01~~09、00，共19次；对于9：09~~89、90~~98、99，共19次）

不考虑前导零，设 dp[n] 表示 n 位数中，每个数码出现的次数。

状态转移方程

考虑 n 位数，分为最高位i和其他位，分别考虑两部分中一种数码出现的次数。则：

对于前 n-1 位，出现次数显然为 dp[n-1]。但由于最高位可以是0~9，故需要乘以10，即为 10 * dp[n-1]。
对于最高位，它出现了 10^(i-1) 次。（例如：1000~~1999，出现的次数即为000~~999的数字个数，即为10^(i-1)）

因此，状态转移方程为：

dp[n] = 10 \cdot dp[n-1] + 10^{n-1}

初始条件

dp[0] = 0，表示0位数中，每个数码出现0次。

别忘了前导0

显然，前导0就是诸如：000(0：这个算正常0)、0001、0002、…、0999等数字中的0。需要单独考虑。对于n位数，前导0的个数为：

10^{n-1} + 10^{n-2} + ... + 10^{1} = \frac{10^{n}-10}{9}

答案的表示

这是题目的难点之一。假设数字为ABCD，规定A不为0。采用从最高位逐步向最低位计算的方式。

首先需要用一个数组存储每一位的出现次数。假设现在在考虑数字d。

首先考虑0000~(A-1)999中，除了最高位的d出现的个数。显然，答案为 A * dp[3]，即（0000~(A-1)999），for x in [0,9]: count[x] += A* dp[3]。
再考虑首先考虑0000~(A-1)999中，最高位中d出现的个数。显然，0,1,...,A-1中，每个数码都出现了10^(4-1)次，因此，for x in [0, A-1]: count[x] += 10^(4-1)。
还需要考虑A000~ABCD，此时，最高位A还出现了BCD + 1次，需要加上。count[A] += BCD + 1。
减去当前的前导0。count[0] -= 10^(4-1)。
此时的问题转化为求BCD中的某个数位的个数，进入了子问题。每一次考虑下一位都会对数位的出现次数统计值进行更新。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long

int a, b;
int dp[15];
int pow10[13];
int countA[10];
int countB[10];

void count(int a, int *cnt)
{
    if (a == 0)
    {
        cnt[0]++;
        return;
    }
    int x = a;
    vector<int> b;
    while (x)
    {
        b.push_back(x % 10);
        x /= 10;
    }
    int bits = b.size();
    for (int i = bits; i >= 1; i--)
    {
        int cur = b[i - 1];
        for (int f = 0; f <= 9; f++)
        {
            cnt[f] += cur * dp[i - 1];
        }
        for (int j = 0; j < cur; j++)
        {
            cnt[j] += pow10[i - 1];
        }
        int y = 0;
        for (int k = i - 1; k >= 1; k--)
        {
            y = y * 10 + b[k - 1];
        }
        cnt[cur] += y + 1;
        cnt[0] -= pow10[i - 1];
        a = y;
    }
    cnt[0]++;
}

signed main()
{
    cin >> a >> b;
    pow10[0] = 1;
    dp[0] = 0;
    for (int i = 1; i <= 12; i++)
    {
        pow10[i] = 10 * pow10[i - 1];
        dp[i] = 10 * dp[i - 1] + pow10[i - 1];
    }
    count(a - 1, countA);
    count(b, countB);
    for (int i = 0; i <= 8; i++)
    {
        cout << countB[i] - countA[i] << ' ';
    }
    cout << countB[9] - countA[9] << endl;
    return 0;
}