count 数字计数(bzoj 1833)

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 ;
}
上一篇:mybatis源码解析7---MappedStatement初始化过程


下一篇:Thrift RPC实战(二) Thrift 网络服务模型