数字计数

数字计数 (奇特的数位dp)

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

这道题就是枚举第i个数位是什么数字，然后乘法原理搞一搞。小心当前枚举的数位是0的情况，需要特判前导零。

#include <cstdio>
using namespace std;

typedef long long LL;
const LL maxl=14;
LL pow[maxl], ans[10];
LL a, b;

void solve(LL x, LL pos){
    if (x==-1){ ans[0]+=1; return; }
    LL now, high, low, flag, len=0;
    for (; pow[len]<=x; ++len);
    for (LL i=0; i<len; ++i){
        now=x%pow[i+1]/pow[i];
        high=x/pow[i+1]; low=x%pow[i];
        for (LL j=0; j<10; ++j){
            if (j) flag=0; else flag=1;
            if (j==now) ans[j]+=((high-flag)*pow[i]+low+1)*pos;
            if (j<now) ans[j]+=((high+1-flag)*pow[i])*pos;
            if (j>now) ans[j]+=((high-flag)*pow[i])*pos;
        }
    }
}

void init_pow(){
    pow[0]=1;
    for (LL i=1; i<=maxl; ++i)
        pow[i]=pow[i-1]*10;
}


int main(){
    init_pow();
    scanf("%lld%lld", &a, &b);
    solve(b, 1); solve(a-1, -1);
    for (LL i=0; i<=9; ++i) printf("%lld ", ans[i]);
    return 0;
}