count 数字计数（bzoj 1833）

时间：2023-08-13 19:31:20

Description

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

Input

输入文件中仅包含一行两个整数a、b，含义如上所述。

Output

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

/*

  令f[i]为i位数(算前导零)中每个数出现的次数(一定是相同的，所以只记录一个就行了)

  有f[i]=f[i-1]*10+10^(i-1)

*/

#include<cstdio>

#include<iostream>

#define lon long long

using namespace std;

lon ans[],f[];

void resolve(lon x,lon pos){

    while(x) ans[x%]+=pos,x/=;

}

void DP(lon x,lon flag){

    int i,j;lon pos,now;

    for(i=,pos=;pos<x;i++,pos*=){//“整数”部分

        for(j=;j<=;j++)

            ans[j]+=f[i-]**flag;

        for(j=;j<=;j++)

            ans[j]+=pos/*flag;

    }

    now=pos/=;i--;

    while(now<x){//“小数”部分

        while(now+pos<=x) {

            lon temp=now/pos;

            resolve(temp,pos*flag);

            for(j=;j<=;j++)

                ans[j]+=f[i]*flag;

            now+=pos;

        }

        pos/=;i--;

    }

}

int main(){

    lon a,b,pos;int i;

    f[]=;

    for(i=,pos=;i<=;i++,pos*=)

        f[i]=f[i-]*+pos;

    cin>>a>>b;

    DP(b+,);DP(a,-);//差分一下

    for(int i=;i<=;i++)

        printf("%lld%c",ans[i],i==?'\n':' ');

    return ;

}

相关文章