
好了,我的数论渣爆了…………
首先[n,m]内的round number显然就是f[m]-f[n-1]
即问0~x内有多少round number;
设x的二进制位数为t;
首先很好分析出在这个范围
若某数的二进制位数<t,则首位1不动,后面组合即可;
然后被卡在当二进制位数为t的round number有多少这招情况;
后来看了别人的解题报告才恍然大悟;
对于x,不算首位的1,只要把当前某一个1改成0,并对后面位数重新01组合就一定小于x,
于是
对于x的每一位1,对后面重新组合即可
显然最终答案不会爆maxlongint
现在想想,其实就是数位dp的思想
var c:array[..,..] of longint;
a:array[..] of longint;
n,m:longint;
procedure prepare; //预处理组合数
var i,j:longint;
begin
c[,]:=;
for i:= to do
begin
c[i,]:=;
c[i,i]:=;
for j:= to i- do
c[i,j]:=c[i-,j]+c[i-,j-];
end;
end; function count(x:longint):longint;
var p,t,i,j,q,s1,s0:longint;
begin
fillchar(a,sizeof(a),);
if x= then exit();
p:=x;
t:=;
while p<> do //十转二
begin
t:=t+;
a[t]:=p mod ;
p:=p shr ;
end;
count:=; //考虑0
for i:= to t- do //当二进制位数小于t
begin
if i mod = then q:=(i-) div + //保证0比1多
else q:=i div ;
for j:=q to i- do
count:=count+c[i-,j];
end;
s0:=;
s1:=;
for i:= to t do //先特判x是否是round number
if a[i]= then inc(s1) else inc(s0);
if s0>=s1 then count:=count+;
s0:=;
s1:=;
for i:=t- downto do
if a[i]= then
begin
for j:=i- downto do //j表示后面可能出现0的个数
if j+s0+>=i--j+s1 then //保证0比1多,i-表示当前位1后面的,+表示将这位1变成0后后面重新组合
count:=count+c[i-,j]
else break;
inc(s1); //别忘统计前面的0,个数,后面的排列情况是由起决定的
end
else inc(s0);
end;
begin
readln(n,m);
prepare;
writeln(count(m)-count(n-)); //经常用到的转化思想
end.