首页 > 代码库 > POJ3252 组合数学
POJ3252 组合数学
POJ3252
问题重述：
求解在区间[start, finish]之间的Round Number的数目。所谓Round Number指的是，二进制表示中0的位数大于等于1的位数的整数。
分析：
1.假如能够分别得到[0, finish] 和 [0, start - 1]区间内的Round Number的数目n1, n2， 那么问题的答案就是n1 - n2. 因此问题可以转化为求解小于n的Round Number的数目。
2.假设整数N的二进制表示为 1,n2,n3,n4,..nk, 则可以把小于N的roundnumber的数目分为两个部分
1)二进制表示位数小于k的Round Number的个数。
容易知道位数为j的Round Number的个数为 C[j-1][0] + C[j - 1][1] + ... + C[j - 1][j / 2 - 1]。
2)位数为k且小于N的Round Number的个数。
M小于N可以理解为：M和N的二进制表示在出现第一个不同位之前的所有位都相同，且mj = 0, nj = 1,(j表示第一个不同位的序号)。因此小于N的Round Number的数目可以通过如下算法计算：找到N中非零位nj = 1， 令mj=0， 且m1 = n1, m2 = n2,.., mj-1 = nj-1,这样只需要令剩余的k - j位的非零位的数目使M满足Round Number的条件即可。
例如对于N=1010010， 1）令M = 100xxxx， 那么M的后4位最多只能有2个1，因此满足该形式的M的个数有C[4][0] + C[4][1] + C[4][2]； 2）令M = 101000X， 则满足条件的M的个数为C[1][0] + C[1][1].
根据以上分析即可求解此问题。
AC代码
1 //Memory: 232K Time: 16MS 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 8 int c[64][64]; 9 int n[64];10 11 void init_c()12 {13 for (int i = 0; i < 64; i++) {14 c[i][0] = 1;15 c[i][i] = 1;16 }17 for (int i = 2; i < 64; i++)18 for (int j = 1; j < i; j++)19 c[i][j] = c[i - 1][j] + c[i - 1][j - 1];20 }21 22 int a[40];23 int len = 0;24 25 int roundNum (long long n)26 {27 len = 0;28 while(n) {29 a[len++] = n % 2;30 n /= 2;31 }32 int ret = 0;33 34 for (int i = 2; i < len; i++) {35 for (int j = 0; j <= i / 2 - 1; j++) {36 ret += c[i - 1][j];37 }38 }39 40 int cnt = 1;41 for (int i = len - 2; i >= 0; i--) {42 if (cnt > len / 2) break;43 if ( a[i] ) {44 for (int j = 0; j <= len / 2 - cnt; j++)45 ret += c[i][j];46 cnt++;47 }48 }49 50 return ret;51 }52 53 int main()54 {55 init_c();56 long long s, f;57 cin >> s >> f;58 cout << roundNum(f + 1) - roundNum(s) << endl;59 return 0;60 }