ATtokiomarine2020E O(rand) 题解

题目链接

点击打开链接

题目解法

首先，\(S\) 一定要是 \(T\) 的子集
先筛出符合条件的 \(a_i\)，即满足 \(S\subseteq a_i\subseteq T\)
令 \(dif\) 为 \(T-S\)，定义数 \(x\) 覆盖第 \(y\) 位为二进制下 \(x\) 的第 \(y\) 位为 \(1\)
现在的问题变成了找到大小 \(\le k\) 的 \(\{a_i\}\) 的子集，使得 \(dif\) 中的每一位都有数覆盖，但不能选出的所有数都覆盖
这显然要容斥，但我一直不会
下面的容斥感觉很妙
显然要枚举不合法的位置集合 \(S\)，这些位置要么没数覆盖，要么所有数都覆盖
而合法的 \(\{a_i\}\) 的子集需要满足 \(x\&S\) 相同，这一步是较妙的
然后可以直接组合数统计了

时间复杂度 \(O(n2^{18})\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=60;
int n,k,S,T,a[N],cnt[1<<18];
LL C[N][N],g[N];
int main(){
    n=read(),k=read(),S=read(),T=read();
    if((S&T)!=S){ puts("0");exit(0);}
    int t=0;
    F(i,1,n){ a[i]=read();if((a[i]&S)==S&&(a[i]|T)==T) a[++t]=a[i];}
    n=t;
    C[0][0]=1;
    F(i,1,n){
        C[i][0]=1;
        F(j,1,min(i,k)) C[i][j]=C[i-1][j-1]+C[i-1][j],g[i]+=C[i][j];
    }
    int dif=S^T;LL ans=0;
    for(;;dif=(dif-1)&(S^T)){
        F(i,1,n) cnt[a[i]&dif]++;
        LL coef=0;
        F(i,1,n) if(cnt[a[i]&dif]) coef+=g[cnt[a[i]&dif]],cnt[a[i]&dif]=0;
        if(__builtin_popcount(dif)&1) ans-=coef;
        else ans+=coef;
        if(!dif) break;
    }
    printf("%lld\n",ans);
    return 0;
}