BZOJ-1662: [Usaco2006 Nov]Round Numbers 圆环数

Description

定义圆环数为：如果一个正整数N的二进制表示中，0的个数大于或等于1的个数，那么N就被称为 "round number" 。求[l,r]中的圆环数个数。

数位DP，f[i][j]表示i位二进制有j个0的方案数。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int l,r;
ll f[40][40];
int calc(int x)
{
    int re=0,i,j,k,c1=0,c0=0,t1,t0,mi;
    for(i=31;~i;--i)
    {
        if((x>>i)&1)
        {
            if(!c1)
            {
                for(j=i-1;j>=0;--j)
                    for(k=0;k<=j;++k) if(k>=j-k+1)
                        re+=f[j][k];
            }
            c1++;
        }
        else if(c1) c0++;
        if(((x>>i)&1)&&c1>1)
        {
            t1=c1-1; t0=c0+1;
            mi=(t1+t0+i)/2+(t1+t0+i)%2;
            for(j=max(0,mi-t0);j<=i;++j) re+=f[i][j];
        }
    }
    return re;
}
int main()
{
    scanf("%d%d",&l,&r);
    f[0][0]=1; int i,j;
    for(i=1;i<=32;++i)
        for(j=0;j<=i;++j)
            f[i][j]=f[i-1][j-1]+f[i-1][j];
    r++;
    printf("%d\n",calc(r)-calc(l));
    return 0;
}