和与或

一道十分好的数位DP
考虑二进制下每一位最多选1个1
详细见代码注释

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int r[12];
int c[12][70];
int dp[70][2048];
int mod=1e9+9;
int dfs(int x,int pos)
{
    if(dp[x][pos]) return dp[x][pos];
    if(x==0) return 1;
    int ps=pos;//预计算ps
    for(int i=1;i<=n;i++) ps|=((c[i][x]==1)<<(i-1));
    dp[x][pos]=dfs(x-1,ps);//此位填0
    for(int i=1;i<=n;i++){//此位填1,枚举用哪个来填
        int t=(pos>>(i-1))&1;//第i位是否可以自由填
        int h= t==1?1:c[i][x];//若可以自由填，赋值1，反正赋值c
        if(h) dp[x][pos]=( dp[x][pos]+dfs( x-1,ps^( (t==0)<<(i-1) ) ) )%mod;//特判编号i是否自由，若不自由，则赋值为不自由 
    }
    return dp[x][pos]%mod;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>r[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=60;j++)
            c[i][j]= (r[i]>>(j-1))&1; //1e18处理到60位即可
    cout<<dfs(60,0);
    return 0;
}