[BZOJ1662] 圆环数

Description

求区间 (a) 到 (b) 中所有二进制中 (0) 的个数大于等于 (1) 的个数的数有多少个。

Solution

设 (f[i][j][k]) 表示从高到低走到下标为 (i) 的位，当前 (0) 的个数为 (j)，(1) 的个数为 (k) 的方案数

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 55;

int a[N],f[N][N][N];

int dfs(int pos,int c0,int c1,int full,int first)
{
    if(pos==0)
    {
        return first || c0>=c1;
    }
    if(~f[pos][c0][c1] && full==0 && first==0) 
    {
        return f[pos][c0][c1];
    }
    int lim=a[pos];
    if(full==0) lim=1;
    int ans=0;
    for(int i=0;i<=lim;i++)
    {
        if(first)
        {
            if(i==0) ans+=dfs(pos-1,c0,c1,full&&i==lim,1);
            else ans+=dfs(pos-1,c0,c1+1,full&&i==lim,0);
        }
        else
        {
            if(i==0) ans+=dfs(pos-1,c0+1,c1,full&&i==lim,0);
            else ans+=dfs(pos-1,c0,c1+1,full&&i==lim,0);
        }
    }
    if(full==0 && first==0) f[pos][c0][c1]=ans;
    return ans;
}

int solve(int n)
{
    int len=0;
    while(n)
    {
        a[++len]=n&1;
        n>>=1;
    }
    memset(f,0xff,sizeof f);
    return dfs(len,0,0,1,1);
}

signed main()
{
    int l,r;
    cin>>l>>r;
    cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}