POJ 3252 组合数学？

大神们的题解我一个都没看懂。。。。。。。。。。。

十分的尴尬

题意：算出闭区间内二进制中0的个数大于等于1的个数的数字有多少个

思路：

组合数学（n小于500的时候都可以出解，只不过高精比较麻烦）。

这道题还算比较仁慈。。。

Discuss里面有一段说得挺好的

（也有人用数位DP、记忆化搜索什么的。。。。 看个人喜好吧）

G++ AC C++WA 鬼知道为什么。。。

// by SiriusRen

#include <bitset>

#include <cstdio>

#include <algorithm>

using namespace std;

bitset<64>n,m;

int C[35][35];

int N,M,maxn=0,maxm=0,cnt1=1,cnt0=0;

int ans=0;

int main()

{

    scanf("%d%d",&N,&M);M++;

    for(int i=30;i>=0;i--){

        if(M&(1<<i))m[i]=1,maxm=max(maxm,i);

        if(N&(1<<i))n[i]=1,maxn=max(maxn,i);

    }

    for(int i=0;i<=31;i++)C[i][0]=1;

    for(int i=1;i<=31;i++)

        for(int j=1;j<=i;j++)

            C[i][j]=C[i-1][j-1]+C[i-1][j];

    for(int i=maxm;i>=0;i--)

        for(int j=i-1;2*j>=i;j--)ans+=C[i-1][j];

    for(int i=maxm-1;i>=0;i--)

        if(m[i]){

            for(int j=maxm-cnt0-cnt1;2*j+2*cnt0+1>=maxm;j--)

                ans+=C[maxm-cnt0-cnt1][j];

            cnt1++;

        }

        else cnt0++;

    cnt1=1;cnt0=0;

    for(int i=maxn;i>=0;i--)

        for(int j=i-1;2*j>=i;j--)ans-=C[i-1][j];

    for(int i=maxn-1;i>=0;i--)

        if(n[i]){

            for(int j=maxn-cnt0-cnt1;2*j+2*cnt0+1>=maxn;j--)

                ans-=C[maxn-cnt0-cnt1][j];

            cnt1++;

        }

        else cnt0++;

    printf("%d\n",ans);

}

看到另一份题解里有这样一句话：

组合数学，一跪一天，爽！

表示赞同