BZOJ 1833 ZJOI 2010 count：數位 DP 統計 0~9 出現次數

問題描述

給定區間 [l, r]，統計 0~9 每個數字在所有整數十進制表示中出現的總次數。l,r ≤ 10¹²。

數位 DP 設計

預處理 f[len][first][digit]：長度為 len、最高位為 first 的所有數中，數字 digit 出現的總次數。
遞推：f[i][k][z] += f[i-1][j][z]（枚舉次高位 j），並加上最高位貢獻 f[i][k][k] += 10^(i-1)。

計算 F(x) = [1,x] 中各數字出現次數

1. 分解 x 為數位數組 d[len..1]
2. 先加長度 < len 的所有數貢獻（查 f 表）
3. 按位處理：對第 i 位，枚舉比 d[i] 小的數字 j，加 f[i][j][*]；再加最高位固定為 d[i] 時的後綴貢獻 x % 10^(i-1) + 1

完整代碼

#include <bits/stdc++.h>
using namespace std;
long long f[15][10][10], pw[15];
long long calc[10], ans[10];

void init() {
    pw[0] = 1;
    for (int i=1; i<=12; ++i) pw[i] = pw[i-1]*10;
    for (int d=0; d<=9; ++d) f[1][d][d] = 1;
    for (int i=2; i<=12; ++i)
        for (int j=0; j<=9; ++j)
            for (int k=0; k<=9; ++k) {
                for (int z=0; z<=9; ++z) f[i][k][z] += f[i-1][j][z];
                f[i][k][k] += pw[i-1];
            }
}

void solve(long long x, long long *res) {
    if (x <= 0) return;
    int d[15], len=0;
    while (x) d[++len] = x%10, x/=10;
    // 長度 < len
    for (int i=1; i=1; --i) {
        for (int j=0; j> l >> r;
    solve(r, ans);
    solve(l-1, calc);
    for (int i=0; i<=9; ++i) cout << ans[i]-calc[i] << (i==9?'\n':' ');
    return 0;
}

關鍵技巧

1. f[i][k][k] += 10^(i-1)：最高位固定為 k 時，該位出現 10^i-1 次
2. 處理最高位時跳過 j=0，避免前導零
3. 後綴貢獻 x % 10^(i-1) + 1：當前位固定為 d[i] 時，後綴範圍 0~x%10^(i-1)，共 +1 個數
4. 預處理到 12 位足夠覆蓋 10¹²

數位 DP 核心思想：將「≤x」分解為「長度更短」+「同長度逐位收緊」，利用預處理表快速累加整段貢獻。