Round Numbers （排列组合）

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 7558		Accepted: 2596

Description

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, Paper, Scissors', 'Ro, Sham, Bo', and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin because it's so hard to toss using hooves.

They have thus resorted to "round number" matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both "round numbers", the first cow wins,
otherwise the second cow wins.

A positive integer N is said to be a "round number" if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many "round numbers" are in a given range.

Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

Input

Line 1: Two space-separated integers, respectively Start and Finish.

Output

Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish

Sample Input

2 12

Sample Output6


题意：给两个数Start 和 Finish，求介于这两个数之间的二进制表示满足0的个数不大于1的个数的整数个数；

思路：另[0,X]表示0到x之间满足题意的正数的个数，则该题即为求[0,Finish]-[0,Start-1];

[0,X]表示0到x之间满足题意的正数的个数求法：(令num[len]表示长度为len的满足题意的整数个数,c[n][m]表示从n个位置中选出m个位置)（假设x的二进制为1010 0100，其长度是8）

1> 二进制形式长度小于8的肯定小于x，假设长度为len(len < 8)

   若len是奇数，len=2*k+1;因第一位都是1，在剩余的2*k位中，0的个数至少是k+1,
   则num[len] = c[2k][k+1]+c[2k][k+2]+.....+c[2k][2k];
   又因为c[2k][0]+c[2k][1]+c[2k][2]+....+c[2k][2k] = 2^2k,
   且c[2k][0]=c[2k][2k],c[2k][1]=c[2k][2k-1]...c[2k][k-1]=c[2k][k+1];推导得num[len]=(2^2k-c[2k][k])/2;
   同理，若len是偶数，num[len]=2^(2k-1)/2;

2> 二进制形式长度等于8时，当把除了第一个1之外的1依次变为0得到的数肯定小于x；例如1010 0100变为前缀是100的肯定小于1010 0100，
   此时0有两个，在后面的5个数中，0至少有2个，所以共有c[5][2]+c[5][3]+c[5][4]+c[5][5]个；1010 0100还可以变为前缀是1010 00的，
   这时0有4个，在后面的两个数中，至少有0个0，共有c[2][0]+c[2][1]+c[2][2]个；还要注意若x本身满足题意，计数器再加1；

 #include<stdio.h>

 #include<string.h>

 const int MS = ;

 using namespace std;

 int power2[MS],c[MS][MS];

 int Binary[MS];

 int RoundNumber(int x)

 {

     memset(Binary,,sizeof(Binary));

     if(x <= ) return ;

     int len,i;

     int number = ;

     int num_1,num_0;//记录二进制中1和0的个数；

     num_1 = ,num_0 = ;

     int tmp = x,cnt = ;

     while(tmp)//将x转化为二进制，其长度为cnt;

     {

         int t =tmp%;

         Binary[cnt++] = t;

         tmp = tmp/;

         if(t == )

             num_1++;

         else num_0++;

     }

     //求长度小于cnt的roundnumber数；

     for(len = ; len <= cnt-; len++)

     {

         if(len%==)

             number += ((power2[len-]-c[len-][(len-)/])>>);

         else number += (power2[len-]>>);

     }

     //求长度等于cnt的roundnumber数；

     if(num_1 <= num_0)

         number ++;

     num_1 = ,num_0 = ;

     for(i = cnt-; i >= ; i--)

     {

         if(Binary[i] == )

         {

             for(int j = i; j >=&& j+num_0+ >= i-j+num_1; j--)

                 number += c[i][j];

             num_1++;

         }

         else num_0++;

     }

     return number;

 }

 int main()

 {

     int n,m;

     for(int i = ; i < MS; i++)

     {

         c[i][] = ;

         c[i][i] = ;

         power2[i] = (<<i);

     }

     for(int i = ; i < MS; i++)

     {

         for(int j = ; j < i; j++)

         {

             c[i][j] = c[i-][j-] + c[i-][j];

         }

     }

     scanf("%d %d",&n,&m);

     int ans = RoundNumber(m) - RoundNumber(n-);

     printf("%d\n",ans);

     return ;

 }

巴特西

Round Numbers （排列组合）

最新文章

热门文章