poj 3252 Round Numbers （组合数）

题目：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即可.

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cmath>
 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<i;j++)
17         c[i][j]=c[i-1][j-1]+c[i-1][j];
18     }
19     return 0;
20 }
21 int chuli(__int64 x)
22 {
23     if(x<=1)
24     return 0;
25     __int64  u;
26     int i,j,k,n;
27     int res=0;
28     u=x;
29     n=0;
30     int num[2]={0};
31     int t=0;
32     while(u)
33     {
34         t=u%2;
35         bir[n]=t;
36         num[t]++;
37         n++;
38         u/=2;
39     }
40     for(i=2;i<n;i++)
41     {
42         if(i%2==1)
43         {
44             k=(i-1)/2;
45             res+=(pow(2,(2*k))-c[2*k][k])/2;
46         }
47         else
48         {
49             k=i/2;
50             res+=pow(2,(2*k)-2);
51         }
52     }
53     if(num[0]>=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 }