python/TangDou/AcWing/DP/ShuWei/POJ3252.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

using namespace std;
const int N = 32;

//整数范围，最大数字的二进制表示，有32位也足够
//状态范围：因为数字0的个数与数字1的个数的差，在中间过程中可能是负数，所以需要做一个偏移处理，映射到自然数的下标空间，也就是双倍空间足够
int f[N][N << 1];
int a[N];

int dfs(int pos, int st, bool lead, bool limit) {
    if (pos == 0) return st >= 32; //大于等于偏移量32，也就是count(0)-count(1)>=0,此时贡献数字1个
    if (!limit && !lead && ~f[pos][st]) return f[pos][st];

    int up = limit ? a[pos] : 1;
    int ans = 0;
    for (int i = 0; i <= up; i++) {
        //前一位是前导零的情况下,本位依然是0
        //(1)st不变，继续传送偏移量32，也就是count(0)-count(1)=0
        //(2)则需要继续传递前导零标识
        if (lead && i == 0)
            ans += dfs(pos - 1, st, true, limit && i == a[pos]); //有前导零就不统计在内
        else
            //场景1：前一位是前导零，本位不是0
            //场景2：前一位不是前导零，本位是0
            //场景3：前一位不是前导零，本位不是0
            //此三种场景，都不需要继续传递前导零标识，即lead=false
            //(1)如果本位是0，则传递st+1
            //(2)如果本位是1，则传递st-1
            ans += dfs(pos - 1, st + (i == 0 ? 1 : -1), false, limit && i == a[pos]);
    }

    if (!limit && !lead) f[pos][st] = ans;
    return ans;
}
int calc(int x) {
    int al = 0;
    while (x) {
        a[++al] = x & 1; //取出二进制的每一位表示，存入数组a中
        x >>= 1;
    }
    // pos=al:从al位开始
    // st=32:目前count(0)-count(1)=32,也就是默认加上了偏移量32
    // lead=true:需要考虑前导0
    // limit=true:贴上界
    return dfs(al, 32, true, true);
}
int main() {
    memset(f, -1, sizeof f);
    // 1 ≤ Start < Finish ≤ 2,000,000,000
    // INT_MAX=2147483647,看来Start和Finish还是在整数范围内
    int a, b;
    while (cin >> a >> b)
        printf("%d\n", calc(b) - calc(a - 1));

    return 0;
}