POJ3252 Round Numbers（不重复全排列）

题目问区间有多少个数字的二进制0的个数大于等于1的个数。

用数学方法求出0到n区间的合法个数，然后用类似数位DP的统计思想。

我大概是这么求的，确定前缀的0和1，然后后面就是若干个0和若干个1的不重复全排列数。。

写得挺痛苦的。。另外A[i][j]表示i个0和j个1的不重复全排列数，即A[i][j]=(i+j)!/i!/j!，这个可以从A[i-1][j]或A[i][j-1]求出来，这样就不用担心乘法溢出了。

#include<cstdio>
#include<cstring>
using namespace std;
long long d[33][33];
long long cnt(int zero,int one,int len){
    long long res=0;
    for(int i=0; i<=len; ++i){
        int j=len-i;
        if(i+zero<j+one) continue;
        res+=d[i][j];
    }
    return res;
}
long long calu(int a){
    int len=31;
    while(len!=-1 && ((a>>len)&1)==0) --len;
    if(len==-1) return 0;
    long long res=0;
    for(int i=1; i<len; ++i){
        res+=cnt(0,1,i);
    }
    int zero=0,one=1;
    for(int i=len-1; i>=0; --i){
        if((a>>i)&1){
            res+=cnt(zero+1,one,i);
            ++one;
        }else{
            ++zero;
        }
    }
    zero=0; one=0;
    for(int i=0; i<=len; ++i){
        if((a>>i)&1) ++one;
        else ++zero;
    }
    return res+(zero>=one);
}
int main(){
    d[0][0]=1;
    for(int i=0; i<32; ++i){
        for(int j=0; j<32; ++j){
            d[i+1][j]=d[i][j]*(i+j+1)/(i+1);
            d[i][j+1]=d[i][j]*(i+j+1)/(j+1);
        }
    }
    int a,b;
    while(~scanf("%d%d",&a,&b)){
        printf("%lld
",calu(b)-calu(a-1));
    }
    return 0;
}