SP3928 MDIGITS - Counting Digits 题解

· · 题解

题意

给定两个整数 a 和 b，在 a 和 b 之间的数字中求每个数字的出现次数。

分析

这是一道数位 \text{dp} 的经典题目。乍看上去，每个数的位数不一样，分开一位位算又太繁琐。但是，不难发现，受位数影响的只有数字 0 的规律而已。这样的话，就可以在数字前先补上前导零，最后再用区间所有数的位数之和减去从 1 到 9 的位数来计算 0 的个数了。

先算一下所有数的位数之和吧。计算一下 a 和 b 的位数 len1 和 len2，接下来如果 len1 = len2 就判掉，否则分以下 3 段算出结果：

  1. 算出 10^{len2 - 1} 到 r 的位数和，即为 (10^{len2 - 1} - r + 1)\times len2；
  2. 算出 l 到 10^{len1} - 1 的位数和，即为 (10^{len1} - r) \times len1；
  3. 算出 10^{len1} 到 10^{len2 - 1} - 1 的位数和，就是 \sum\limits_{i = len1}^{len2 - 1}10^{i - 1} \times 9i

接下来考虑差分，算出从 1 到 x 的 y 的出现次数。令 dp_{i, j, k} 表示前 i 位中最前一位的值为 j 的时候数字 k 的出现次数（奇怪的方法），那么有：

若 l = k，则 dp_{i + 1, k, l} 要加上 dp_{i, j, l} + 10^{i - 1}（容易理解，10^{i - 1} 是第一位的 k 贡献的）

否则，dp_{i + 1, k, l} 要加上 dp_{i, j, l} （一样容易理解，l 的个数只能靠后面的 i 位来贡献）

有了这些之后，就可以枚举每一位与当前这一位一个个加上这一位的值（方法和求 dp 一模一样）来求出答案了。

代码

#include <stdio.h> 
#include <string.h>
#define lld long long 
lld dp[30][10][10];
lld pow10[20];
lld ans[10];
lld calc(lld x, lld y) {
    if (x < 0) return 0; else if (x == 0) return 0; // 判掉奇奇怪怪的特殊情况
    int len; for (len = 0; pow10[len] <= x; ++ len); // x 的位数即为 len
    lld ans = 0, bit;
    for (int i = 1; i <= len; ++ i) {
        bit = x / pow10[len - i] % 10;
        for (lld j = 0; j < bit; ++ j) ans += dp[len - i + 1][j][y]; // 加上这些dp值
        if (bit == y) ans += x % pow10[len - i]; // 特判最后部分
    }
//  printf("%lld %lld: %lld\n", x, y, ans);
    return ans;
}
lld AllDigits(lld l, lld r) {
    int lenl, lenr;
    for (lenl = 0; pow10[lenl] <= l; ++ lenl);
    for (lenr = 0; pow10[lenr] <= r; ++ lenr);
    if (lenl == lenr) return (r - l + 1) * lenl; // 判掉特殊情况
    lld ans = (r - pow10[lenr - 1] + 1) * lenr + (pow10[lenl] - l) * lenl;
    for (int i = lenl + 1; i < lenr; ++ i) ans += pow10[i - 1] * 9 * i;
    return ans;
}
int main() {
    pow10[0] = 1;
    for (int i = 1; i <= 12; ++ i) pow10[i] = pow10[i - 1] * 10;
    for (int i = 0; i <= 9; ++ i) dp[1][i][i] = 1;
    for (int i = 1; i <= 12; ++ i)
        for (int j = 0; j <= 9; ++ j)
            for (int k = 0; k <= 9; ++ k)
                for (int l = 0; l <= 9; ++ l)
                    if (l == k) dp[i + 1][k][l] += dp[i][j][l] + pow10[i - 1];
                    else dp[i + 1][k][l] += dp[i][j][l]; // 前文所述的dp
    lld a, b;
    for(; ~scanf("%lld%lld", & a, & b); ) {
        if (!a && !b) return 0;
        memset(ans, 0, sizeof(ans));
        if (a > b) a ^= b ^= a ^= b;
        for (int i = 1; i <= 9; ++ i) ans[i] = calc(b + 1, i) - calc(a, i); // 差分
        ans[0] = AllDigits(a, b); for (int i = 1; i <= 9; ++ i) ans[0] -= ans[i]; // 算出所有的，减去其他的
        for (int i = 0; i <= 9; ++ i) printf("%lld ", ans[i]);
        puts("");
    }
}