poj3252

时间:2023-03-09 14:59:28
poj3252

好了,我的数论渣爆了…………

首先[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.