题解：AT_tokiomarine2020_e O(rand)

· · 题解

Sol

首先有个很显然的无解情况是 S \& T\ne S。

那么，我们选的所有数都要满足 A\&S=S\land A\mid T=T。先把这些数选出来，不符合的省略。

考虑 S\oplus T 的部分，为 1 的位就要求选出来的数中，既有这一位上为 1 的，又有这一位上为 0 的。这个不好搞，容斥一下，就是这一位上全为 1 或者全为 0 的选法均不合法。

考虑容斥，每次钦定一个位集合不合法，容斥系数即为集合大小，那么就要求选出来的数在这些给定位上全为 1 或全为 0，不难发现也就是要求与位集合按位与之后相等，开个桶存相等的个数即可，然后对每个桶枚举选的个数组合计数即可。

Code

const int N=55;

int n,k,m;
ll s,t,a[N];
int c,u[N],x[N];
ll f[1ll<<18],ans;
map<int,int> cnt;
ll C[N][N];

inline void Main(){
    cin>>n>>k>>s>>t;
    rep(i,1,n)cin>>a[i];
    if(s&t^s)return put(0),void();
    for(ll i=s^t;i;i^=i&-i)u[c++]=i&-i;
    rep(i,1,n)if((a[i]&s)==s&&(a[i]|t)==t){
        ++m;
        repl(j,0,c)x[m]|=(!!(a[i]&u[j]))<<j;
    }
    C[0][0]=1;
    rep(i,1,n){
        C[i][0]=1;
        rep(j,1,n)C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    repl(s,0,1<<c){
        cnt.clear();
        rep(i,1,m)++cnt[x[i]&s];
        for(auto i:cnt)rep(j,1,k)ans+=(__builtin_popcount(s)&1?-1:1)*C[i.sec][j];
    }
    put(ans);
}