POJ 3252 Round Numbers

好久不写，这个题目又弄了几个小时，水平还是有限。

这道题我用组合数学来做，如果要求区间[a,b]的个数，先求出[2,a)的个数和[2,b]的个数，两者相减。

首先我们假设求 [1000，10000)(二进制表示)这个区间，那么在这个区间里高位都是为1的，剩下3位里面必须至少有两位为0。故为C(3,2)+C(3,3)=C(3,0)+C(3,1),因为左边和右边之和为2^3(二项式定理),故解为2^2。

那如果是[10000,100000)，同理可以得到有C(4,2)+C(4,3)+C(4,4),因为 C(3,0)+C(3,1)+C(4,2)+C(4,3)+C(4,4)=2^4，所以前面那个式子的和为(2^4-C(4,2))/2.由上面可以分为奇偶情况来分别计算。

再假设要求[2,20)区间的个数，20=10111，那么我们先求出[10,10000)(二进制)这个就是上面讨论的情况了。然后再取为1的情况10011，右边第二位为1，如果为0，则有1000**,后面两位可以随意取，然后根据1/0的情况像上面一样讨论。然后再后移找为1的情况，直到完成。

代码：

[cpp]
#include<iostream>
#include<cmath>
using namespace std;
int dp[35][35], sqr[35];
void Cn() //二的幂，组合
{
     int i,j;
     memset(dp,0,sizeof(dp));
     dp[0][0]=1;
     for( i=1;i<=32;i++)
      for( j=0;j<=i;j++){
          if(j==0) dp[i][j]=1;
          else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
      }
     sqr[0]=1;
     for(i=1;i<=31;i++)
       sqr[i]=sqr[i-1]*2;
}

int Fn(int k,int d) // k个数,原来0比1多d个
{
    if(k-d<=0) return sqr[k];

    int sum=0,i;
    if((k-d)%2) i=(k-d+1)/2;
    else i=(k-d)/2;
    for( ;i<=k;i++)
         sum+=dp[k][i];
    return sum;
}

void Cal(int n,int&sum)
{
    int temp,num[35],i,j;
    int one=0,zero=0;

    temp=n;
    for( i=0;temp;i++){
           if( temp&1) num[i]=1;
           else   num[i]=0;
           temp>>=1;
    }

    for( j=1;j<i-1;j++){ //i是二进制的长度。
         if(j%2) sum+=sqr[j-1];      //奇偶的情况分析
       else sum+=(sqr[j]-dp[j][j/2])/2;
    }

    one=0,zero=0;
    for( j=i-2;j>=0;j--){
         if( num[j]){
             sum+=Fn(j,zero-one);
             one++;
         }
         else zero++;
    }
    if(one+1<=zero) sum++;
}

int main()
{
    int a,b,start,finish;
    Cn();
    while( scanf("%d%d",&start,&finish)!=EOF){
           a=b=0;
           Cal(start-1,a);
           Cal(finish,b);
           printf("%d\n",b-a);
    }
    return 0;
}

补充：软件开发 , C++ ,