poj3252.cpp

来自「poi3252」· C++ 代码 · 共 53 行

//#include <algorithm>
#include <iostream>

using namespace std;

static int infoc[64][64];
int max(int a,int b)
{
	return a>b?a:b;
}
static int counum(int b, int z, unsigned int top) {
    int ans = 0;

    if (z > b || top == 0) return 0;
    if (top >= (1U << b)) {
        for (int j = max(z, 0); j <= b; j++)
            ans += infoc[b][j];
        return ans;
    }

    ans += counum(b - 1, z - 1, top);
    unsigned int h = 1U << (b - 1);
    if (top > h && b > z)
        ans += counum(b - 1, z, top - h);
    return ans;
}

static int counumrange(int b, int z, unsigned int start, unsigned int end) {
    if (start >= end) return 0;
    return counum(b, z, end) - counum(b, z, start);
}

int main() {
    int i;
	for (i = 0; i < 64; i++) {
        infoc[i][0] = infoc[i][i] = 1;
        for (int j = 1; j < i; j++)
            infoc[i][j] = infoc[i - 1][j - 1] + infoc[i - 1][j];
    }

    unsigned int f, l;
    int ans = 0;
    cin >> f >> l;
    for (i = 1; i <= 31; i++) {
        unsigned int f1 = max(f, 1U << (i - 1));
        ans += counumrange(i, (i + 1) / 2, f1, l + 1);
    }
    cout << ans << "\n";
    return 0;
}