和与或

好久没有复习数位dp了，今天来补下这个题
链接

思路：简化一下即是求的对数满足且,很明显这是一个数位dp，即f[len][limit1][limit2]来表示，那么本题就可以考虑将每个数进行状态压缩

对于limit，0表示有限制，1表示无限制
state表示1~n的每个r[i]对x位的取值
state|limit：表示当前位限制对下一位的影响
如果当前没有限制，则取1
如果有限制，且可以放1，那么当前位保持限制，其他位解除限制

#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 );//当前位填0
    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);
}