题目：http://poj.org/problem?id=3252

题意：求区间Start..Finish 之间 二进制0比1多或相等的数字的个数

借鉴一下别人的思路吧。。。

思路：记f(start, finish)为[start, finish]里Round Number的个数,那么要求f(start,finish),只需用f(0,finish)-f(0,start-1)即可,则问题转化为给定x,求出f(0,x).

假定x=(10101101),其长度为8位.而[0,x]中的数可分为二进制长度小于8位的和二进制长度等于8位的.

首先看二进制长度小于8位的,即求出长度在[0,7]区间内的Round Number个数.对于长度为len的二进制（最高位一定是1）,记其Round Number个数为R(len),可按照len的奇偶性分两种情况.

1. len=2k+1时,去掉最高位的1,剩下2k位里至少要有k+1个0,用C(n,m)表示n个位置选m个位置的方法.

有R(len)=C(2k,k+1)+C(2k,k+2)+…+C(2k,2k)=1/2*(2^(2k)-C(2k,k))

2. 同理可得,len=2k时,R(len)=1/2*(2^(2k-1))

接下来看二进制长度为8位的.

首先判断x本身,然后对于x的二进制,若将其中除了最高位的1以外的任意一个或多个1变为0,得到的数一定小于x,那么就能通过这种方法得到二进制位数和x相等且比x小的Round Number个数了.

最后将两部分结果求和即可.

精度方面,2000000000<2*1024*1024*1024=2^31,故用31位表示数组,又第一位总为1,所以组合数只用求到30,C(30,k) (0<=k<=30) <= 2^30,故用int即可.

1 #include 
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int c[35][35]; 6 int bir[35]; 7 int init() 8 { 9     int i,j;10     for(i=0;i<35;i++)11     {12         c[i][0]=c[i][i]=1;13     }14     for(i=2;i<35;i++)15     {16         for(j=1;j
         
          =num[1])54     {55         res++;56     }57     int n1=1;58     int n0=0;59     for(i=n-2;i>=0;i--)60     {61         if(bir[i])62         {63             for(j=i;j>=0&&j+n0+1>=i-j+n1;j--)64             {65                 res+=c[i][j];66             }67             n1++;68         }69         else n0++;70     }71     return res;72 }73 int main()74 {75     __int64 a,b;76     init();77     scanf("%I64d %I64d",&a,&b);78     printf("%d\n",chuli(b)-chuli(a-1));79     return 0;80 }