数字计数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1612 字
求[a,b]中所有整数里，数码0~9各自出现
一本通
练习
正文

/*
原题：数字计数（一本通 5.3 练习 4，ZJOI 2010）
题意：求 [a,b] 中所有整数里，数码 0~9 各自出现的总次数，输出 10 个整数。
思路：数位 DP，state=(pos,started,tight)，返回 {本状态合法数字个数, 各数码出现次数}。
     前导零不计入“数字”；当前位放下的真实数字 d 会为后续每个完整数贡献一次 d。
     答案[d] = f(b).occ[d] - f(a-1).occ[d]。
复杂度：时间 O(log10 b * 10)，空间 O(log10 b)
易错点：前导零不能算作数码 0；用 cnt 给当前位的数字计数。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dig[15];
bool vis[15][2][2];
struct Res{
    ll cnt;
    ll occ[10];
};
Res memo[15][2][2];
int len;
Res dfs(int pos, bool started, bool tight){
    if(pos == len){
        Res r;
        r.cnt = 1;
        for(int i = 0; i < 10; i++) r.occ[i] = 0;
        return r;
    }
    if(vis[pos][started][tight]) return memo[pos][started][tight];
    Res tot;
    tot.cnt = 0;
    for(int i = 0; i < 10; i++) tot.occ[i] = 0;
    int up = tight ? dig[pos] : 9;
    for(int d = 0; d <= up; d++){
        bool ns = started || d != 0;
        Res sub = dfs(pos + 1, ns, tight && d == up);
        tot.cnt += sub.cnt;
        for(int i = 0; i < 10; i++) tot.occ[i] += sub.occ[i];
        if(ns) tot.occ[d] += sub.cnt;
    }
    vis[pos][started][tight] = true;
    return memo[pos][started][tight] = tot;
}
Res f(ll n){
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % 10;
        t /= 10;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(vis, 0, sizeof(vis));
    return dfs(0, false, true);
}
int main(){
    ll a, b;
    cin >> a >> b;
    Res R = f(b), L = f(a - 1);
    for(int i = 0; i < 10; i++){
        cout << R.occ[i] - L.occ[i] << (i == 9 ? "" : " ");
    }
    cout << "\n";
    return 0;
}
数字计数

正文

一本通·提高篇的其它内容
