POJ-3252 Round Numbers組合せ数学
7036 ワード
この問題は,与えられたa,b区間内の複数の数がバイナリ表現法内の0の数の余分な1の数を満たすことを意味する.詳細は、コードを参照してください.
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[40][40];
void pre()
{
c[0][0] = 1;
for (int i = 1; i <= 30; ++i) {
c[0][i] = 1;
for (int j = 1; j <= 30; ++j) {
c[j][i] = c[j][i-1] + c[j-1][i-1];
}
}
}
int deal(int x)
{
// 1 ， 100110， [0, 11111] ，
// ， ， 1 6
if (x <= 1) return 0;
int pos, ret = 0;
for (int i = 30; i >= 0; --i) {
if ((1 << i) & x) {
pos = i;
break;
}
}
// printf("pos = %d
", pos);
// 1 pos+1 ， x 100110， pos = 5， 5,4,3,2
for (int i = pos; i >= 2; --i) {
for (int j = (i+1) >> 1; j <= i-1; ++j) {// 5， 1， 1
// pos-1 (pos+1)/2 0， pos-1 0
// printf("%d %d
", j, i-1);
ret += c[j][i-1];
}
}
// printf("ret = %d
", ret);
// [100000, 100110]， 1
// [100000, 100011], [100100, 100101], [100110, 100110]， ，
// ， 1 ， 1 ， 0
int one = 1, zero, k;
for (int i = pos-1; i >= 0; --i) { // 1
if ((1 << i) & x) { // i
zero = pos+1-i-one;
k = max(0, (i+one-zero+1)>>1);
for (int j = k; j <= i; ++j) {
ret += c[j][i];
}
++one;
}
} // ， 1， 0 ， 1
return ret;
}
int main()
{
int a, b;
pre();
while (scanf("%d %d", &a, &b) == 2) {
printf("%d
", deal(b+1) - deal(a));
}
return 0;
}