牛客每日一题 和与或(数位DP)

传送门

也就是每一位二进制只能放在这个数中的某一个上面

每位数字不能超过,我们发现这非常像数位的过程

现在简化一下问题

求的对数满足且

很明显这就是一个数位,表示

枚举到二进制第位,卡不卡上界,卡不卡上界

然后只需要暴力考虑当前位二进制填还是填

填的话填在还是填在,然后更新上下界范围即可。

回到这个问题

发现完全就是一样的问题,只不过变成了个数

当然你也可以去转移

不过这里用二进制压缩一下状态会更好看

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
int f[63][1<<12],r[13],n,bit[64];
int dfs(int x,int limit)
{
    if( x<0 )    return 1;
    if( f[x][limit]!=-1 )    return f[x][limit];
    int state = 0, ans = 0;
    for(int i=1;i<=n;i++)
        if( r[i]&bit[x] )    state |= bit[i];//枚举当前位置的枚举范围
    ans += dfs(x-1,limit|state );
    for(int i=1;i<=n;i++)//枚举这个1填在哪个数上面 
    {
        if( bit[i]&limit )//已经没有限制了,可以填 
            ans += dfs(x-1,limit|state );//取1,其他位有1的也变成无限制 
        else if( bit[i]&state )//当前位有限制,且可以放1
            ans += dfs(x-1,(limit|state)^bit[i] );//当前位置保持限制,其他位解除限制 
    }
    return f[x][limit] = ans%mod;
}
signed main()
{
    bit[0] = 1;
    for(int i=1;i<=62;i++)    bit[i] = bit[i-1]*2;
    memset( f,-1,sizeof f );
    cin >> n;
    for(int i=1;i<=n;i++)    scanf("%lld",&r[i] );
    cout << dfs(61,0);
}