数字统计问题题解

一、题目分析

题目要求计算区间 [a, b] 内所有数字中0-9每个数字的出现次数。例如，输入1024和1032时，需统计列表中每个数字的出现次数。关键在于高效计算大范围区间内的数字出现频率。

二、算法思路

1. 数位动态规划（数位DP）：通过预处理和状态转移，快速计算数字在各个数位上的出现次数。
2. 状态定义：dp[i][j][k] 表示长度为i的数中，最高位为j，数字k的出现次数。
3. 分治思想：将区间 [a, b] 的统计转化为 [0, b] - [0, a-1] 的统计，避免重复计算。

三、代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define Abigail inline void
typedef long long LL;

const int N = 10;  // 数字0-9

LL l, r, pw[N + 9];  // pw[i] = 10^i

// 预处理10的幂次
void Get_pw() {
    pw[0] = 1;
    for (int i = 1; i <= N; ++i) pw[i] = pw[i - 1] * 10;
}

LL dp[N + 9][N + 9][N + 9];  // dp[i][j][k]: 长度为i，最高位为j的数中k的出现次数

// 预处理DP数组
void Get_dp() {
    for (int i = 0; i < N; ++i) dp[1][i][i] = 1;  // 一位数时，数字本身出现1次
    for (int i = 2; i <= N; ++i)  // 处理i位数
        for (int j = 0; j < N; ++j)  // 最高位为j
            for (int k = 0; k < N; ++k) {  // 统计数字k的出现次数
                for (int t = 0; t < N; ++t) dp[i][j][t] += dp[i - 1][k][t];  // 低位继承i-1位数的状态
                dp[i][k][k] += pw[i - 2];  // 最高位为k时，低位每个位置k的出现次数
            }
}

LL ans[N + 9];  // 存储0-9的出现次数
int a[N + 9], ca;  // a数组存储数字各位，ca为位数

// 计算[0, mx]中各数字的出现次数，v为±1（用于区间相减）
void Get_ans(LL mx, int v) {
    LL t = mx;
    for (ca = 0; mx; mx /= 10) a[++ca] = mx % 10;  // 分解数字各位
    
    // 处理长度小于ca的数
    for (int i = 1; i < ca; ++i)
        for (int j = 1; j < N; ++j)  // 最高位不能为0（除了一位数）
            for (int k = 0; k < N; ++k)
                ans[k] += dp[i][j][k] * v;
    
    // 处理长度等于ca的数
    for (int i = ca; i >= 1; --i) {
        for (int j = 0; j < a[i]; ++j) {  // 枚举当前位可能的数字（小于a[i]）
            if (!j && i == ca) continue;  // 最高位不能为0
            for (int k = 0; k < N; ++k)
                ans[k] += dp[i][j][k] * v;
        }
        ans[a[i]] += (t % pw[i - 1] + 1) * v;  // 统计当前位为a[i]时的出现次数
    }
}

// 初始化预处理
Abigail start() {
    Get_pw();
    Get_dp();
}

// 处理一组输入
Abigail work() {
    for (int i = 0; i < N; ++i) ans[i] = 0;
    if (l > r) swap(l, r);  // 确保l <= r
    Get_ans(r, 1);        // 计算[0, r]的统计
    Get_ans(l - 1, -1);   // 减去[0, l-1]的统计，得到[l, r]
}

// 输出结果
Abigail outo() {
    for (int i = 0; i < N - 1; ++i)
        printf("%lld ", ans[i]);
    printf("%lld\n", ans[N - 1]);
}

int main() {
    start();
    while (~scanf("%lld%lld", &l, &r) && l + r) {  // 输入非0时处理
        work();
        outo();
    }
    return 0;
}

四、代码解释

1. 预处理阶段：

   • Get_pw() 计算10的各次幂，用于数位分解；
   • Get_dp() 预处理DP数组，存储不同长度和最高位下各数字的出现次数。

2. 核心统计函数Get_ans：

   • 分解数字各位，分别处理长度小于和等于当前数字长度的情况；
   • 利用预处理的DP数组快速累加各数位的出现次数，通过v参数实现区间相减。

3. 区间统计：

   • work() 函数将区间 [l, r] 转换为 [0, r] - [0, l-1]，避免重复计算；
   • 调用Get_ans两次，通过正负参数相减得到最终结果。

五、示例解析

输入：1 10

1. 计算[0,10] - [0,0]：

   • [0,10]中0出现2次（0,10），1出现2次（1,10），其他数字各出现1次；
   • [0,0]中0出现1次；
   • 相减后得到1-10中各数字出现次数：0出现1次，1出现2次，其他各1次。

2. 输出：1 2 1 1 1 1 1 1 1 1

六、复杂度分析

• 预处理复杂度：O(N³)，其中N=10，可忽略不计；
• 单次查询复杂度：O(位数×N²)，位数最多8位（1e8），故单次查询为O(1)；
• 总体复杂度：O(500×8×10²)=O(40000)，可高效处理500组输入。

七、关键技巧

1. 数位DP状态定义：通过dp[i][j][k]存储长度为i、最高位为j时数字k的出现次数；
2. 区间转换：将 [l, r] 转化为 [0, r] - [0, l-1]，简化边界处理；
3. 预处理优化：提前计算DP数组，避免重复计算相同数位状态。