1833: [ZJOI2010]count 数字计数 - BZOJ

时间:2022-09-15 11:17:22

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(b)-f(a-1)

然后就是比较简单的数位dp

f[i,j]表示长度为i以j开头0到9各个数字的出现次数

先算出全部的,再减去不合法的

不合法的就是枚举,减去从第i位开始超出n的情况,注意减去比第i位更高的数字(一开始就这样WA的)

 type
node=array[..]of int64;
var
f:array[..,..]of node;
ten:array[..]of int64;
a,b:int64; operator +(a,b:node)c:node;
var
i:longint;
begin
for i:= to do
c[i]:=a[i]+b[i];
end; operator -(a,b:node)c:node;
var
i:longint;
begin
for i:= to do
c[i]:=a[i]-b[i];
end; operator *(a:node;b:int64)c:node;
var
i:longint;
begin
for i:= to do
c[i]:=a[i]*b;
end; function ff(x:int64):node;
var
s:array[..]of longint;
i,j,len:longint;
fff:node;
begin
fillchar(ff,sizeof(ff),);
fillchar(fff,sizeof(fff),);
for i:= to do
begin
s[i]:=x mod ;
x:=x div ;
end;
for i:= downto do
if s[i]<> then break;
len:=i;
for i:= to len do
for j:= to do
ff:=ff+f[i,j];
for i:=len downto do
begin
for j:=s[i]+ to do
ff:=ff-f[i,j]-fff*ten[i];
inc(fff[s[i]]);
end;
end; procedure print(a:node);
var
i:longint;
begin
for i:= to do
write(a[i],' ');
write(a[]);
end; procedure main;
var
i,j,k:longint;
begin
read(a,b);
ten[]:=;
for i:= to do
ten[i]:=ten[i-]*;
for i:= to do
for j:= to do
begin
for k:= to do
f[i,j]:=f[i,j]+f[i-,k];
inc(f[i,j,j],ten[i]);
end;
print(ff(b)-ff(a-));
end; begin
main;
end.