SPOJ BALNUM

一开始题看错了。。。dp[pos][sets][viss]，其中sets表示出现次数，viss表示出现没有。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

long long t,l,r,dp[][][],bit[],ret=;

void get_bit(long long x)

{

    ret=;

    while (x) {bit[++ret]=x%;x/=;}

}

long long check(long long sets,long long viss)

{

    for (long long i=;i<=;i++)

    {

        if (!(viss&(<<i))) continue;

        if ((i&) && (sets&(<<i))) return ;

        if ((!(i&)) && (!(sets&(<<i)))) return ;

    }

    return ;

}

long long dfs(long long pos,long long sets,long long viss,bool flag)

{

    if (!pos) return check(sets,viss);

    if ((!flag) && (~dp[pos][sets][viss])) return dp[pos][sets][viss];

    long long ans=,up=flag?bit[pos]:;

    for (long long i=;i<=up;i++)

        ans+=dfs(pos-,sets^(<<i),viss|(<<i),flag&&(i==up));

    if (!flag) dp[pos][sets][viss]=ans;

    return ans;

}

long long work(long long x)

{

    if (!x) return ;

    get_bit(x);long long ans=;

    for (long long i=;i<=ret-;i++)

        for (long long j=;j<=;j++)

            ans+=dfs(i-,<<j,<<j,);

    for (long long j=;j<=bit[ret]-;j++)

        ans+=dfs(ret-,<<j,<<j,);

    ans+=dfs(ret-,<<bit[ret],<<bit[ret],);

    return ans;

}

int main()

{

    scanf("%lld",&t);memset(dp,-,sizeof(dp));

    for (long long i=;i<=t;i++)

    {

        scanf("%lld%lld",&l,&r);

        printf("%lld\n",work(r)-work(l-));

    }

    return ;

}