題目描述

如果一個(gè)正整數(shù)的二進(jìn)制表示中，00的數(shù)目不小于11的數(shù)目，那么它就被稱(chēng)為「圓數(shù)」。

例如，99的二進(jìn)制表示為10011001，其中有22個(gè)00與22個(gè)11。因此，99是一個(gè)「圓數(shù)」。

請(qǐng)你計(jì)算，區(qū)間[l,r][l,r]中有多少個(gè)「圓數(shù)」。

輸入格式

一行，兩個(gè)整數(shù)ll和rr。

輸出格式

一行，一個(gè)整數(shù)，表示區(qū)間[l,r][l,r]中「圓數(shù)」的個(gè)數(shù)。

樣例

輸入：2　122　12　　　　　　　　　輸出： 66

思路

顯然這道題又是一道數(shù)位DP。但是這個(gè)題的難點(diǎn)和特殊之處就在于它是在二進(jìn)制下處理的。這就需要我們重新揣度此題的狀態(tài)。

設(shè)f[i][j][k]f[i][j][k]表示一個(gè)有ii位，且其中包括jj個(gè)11，且從右往左數(shù)第ii個(gè)數(shù)是kk的圓數(shù)的個(gè)數(shù)。這個(gè)如何轉(zhuǎn)移呢？

顯然的是，若j<ij<i,　　f[i][j][0]=f[i?1][j][0]+f[i?1][j][1]f[i][j][0]=f[i?1][j][0]+f[i?1][j][1]，若j!=0j!=0，　則f[i][j][1]=f[i?1][j?1][0]+f[i?1][j?1][1]f[i][j][1]=f[i?1][j?1][0]+f[i?1][j?1][1] （這個(gè)感性理解一下？）

最后就分成兩種情況處理：

1.將位數(shù)小于cnt位的圓數(shù)累加到答案中

2.和其他數(shù)位DP類(lèi)似，考慮用添數(shù)的方法解決問(wèn)題。若當(dāng)前遍歷到該位為11，那么就存在該位為00的情況，這時(shí)候再枚舉11的位數(shù)，考慮還是否能構(gòu)成圓數(shù)，若能構(gòu)成，累加答案即可。

最后前綴和統(tǒng)計(jì)答案即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
int l, r;
ll f[35][35][2];
inline int read(void){
    int f = 1, x = 0;char ch;
    do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
    do{ x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}
inline void _init(void){
    f[1][0][0] = 1, f[1][1][1] = 1;//初始化
    for (int i = 2; i <= 32;++i){
        for (int j = 0; j <= i;++j){
            if(j<i) f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1];//若既有0又有1或只有0
            if(j) f[i][j][1] = f[i - 1][j - 1][0] + f[i - 1][j - 1][1];//若有1或全部是1
        }
    }
    return;
}
inline ll calc(int x){
    int bn[35], cnt = 0;
    ll res = 0;
    if(x==0) return 1;
    while(x){
        bn[++cnt] = x & 1;
        x >>= 1;
    }//二進(jìn)制拆分
    for (int i = 1; i < cnt;++i){
        for (int j = 0; j <= (i >> 1); ++j)
            res += f[i][j][1];
    }//統(tǒng)計(jì)小于cnt位的圓數(shù)，(i>>1)這個(gè)就是保證了所得的數(shù)一定為圓數(shù)
    int s0 = 0, s1 = 1;//s1一定要賦值為1，因?yàn)闊o(wú)論如何我們討論的數(shù)都是大于1的（為0的情況在開(kāi)頭就舍掉了)
    for (int i = cnt - 1; i >= 1;--i){
        if(bn[i]) for (int j = 0; j <= i;++j){
            if(s0+i-j>=s1+j) res += f[i][j][0];//已確定的0的個(gè)數(shù)+枚舉的0的個(gè)數(shù)>=已確定的1的個(gè)數(shù)+枚舉的1的個(gè)數(shù)
        }//                                          s0        +  i  -  j   >=     s1       +     j
        bn[i] ? ++s1 : ++s0;
    }
    return res;
}
int main(){
    l = read(), r = read();
    _init();
    printf("%lld\n", calc(r + 1) - calc(l));
    return 0;
}