【数位DP】数字计数

原题链接：https://www.luogu.com.cn/problem/P2602

在这里插入图片描述

状态表示f[i][j][k]：

• 集合：数字[1:i]中第j位上k出现的次数
• 属性：Num

状态计算

i共十位，假设第j位为d，高位为l，低位为e，i可以表示成l d r。 [1:i]之间的数字可以表示成x d y，要求的是k出现的次数，对于[1:i]进行划分： 划分一：高位x小于a，根据k的值进一步划分：

• 情况1：k取值非零。对于高位x任何在[0:l-1]之间的取值，第j位都可以取到k，取完之后，低位可以取

中的任何数，比如，j为第4时，低位有[001:999]共1000种取法。集合中第j位上值为k的数字共有l*pow(10,j-1)个，即第j位上k出现了l*pow(10,j-1)次。

• 情况2：k取值为零。低位可以取

中的任何数，高位的取值范围为[1:l-1]，因为如果高位都是0，那么第d位会被省略，比如000 0 123，会写作123，第4位和更高位上的0不会被考虑。高位共l-1种取法，集合中第j位上值为k的数字共有(l-1)*pow(10,j-1)个，即第j位上k出现了(l-1)*pow(10,j-1)次。

划分二：高位x等于a，对划分二进一步划分：

• 情况1：d < k，无解，在高位x等于a的情况下，[1:i]没有数字的第j位上等于k。
• 情况2：d == k，高位和第j位只有一种选法，低位可以取[0:r]，共r+1个数字的第j位上等于k。
• 情况3：d > k，高位和第j位只有一种选法，低位可以取[0:pow(10,j-1)-1]，共pow(10,j-1)个数字的第j位上等于k。

以上划分是对[1:i]中的数字，依据高位和第j in [1:len(i)]位进行划分。 划分一中元素的数量与k相关，由于条件互斥，所以情况只会发生一个：

• 如果k为零，那么划分一的集合中，数字的数量为l*pow(10,j-1)
• 如果k非零，那么划分一的集合中，数字的数量为(l-1)*pow(10,j-1)]

划分二中元素的数量与d和k大小关系相关，由于条件互斥，所以情况只会发生一个：

• 如果d < k，那么划分二的集合中，数字的数量为0
• 如果d == k，那么划分二的集合中，数字的数量为r+1
• 如果d > k，那么划分二的集合中，数字的数量为pow(10,j-1)

划分一和划分二依据高位进行划分，[1:i]的高位x一定小于等于i的高位，因此最终的集合属性Num是两个划分下集合Num的加和。状态转移操作可以利用乘除法在O(1)时间内求出，不需要为状态源开辟空间。

#include "bits/stdc++.h"

using namespace std;

int getLen(int i) {
    int res = 0;
    while (i) {
        res++;
        i /= 10;
    }
    return res;
}

int solve(int i, int k) {
    int res = 0;
    for (int j = 1; j <= getLen(i); j++) {
        int p = pow(10, j - 1);
        int l = i / (p * 10);
        int r = i % p;
        int d = i / p % 10;
        if (k)res += l * p;
        else res += (l - 1) * p;
        if (d == k)res += r + 1;
        if (d > k)res += p;
    }
    return res;
}

int main() {
    int a, b;
    cin >> a >> b;
    while (a) {
        if (a > b)swap(a, b);
        for (int i = 0; i <= 9; i++)
            cout << solve(b, i) - solve(a - 1, i) << ' ';
        puts("");
        cin >> a >> b;
    }
}