题解：P11777 [COTS 2013] 集合求解 / BOMBONI

· · 题解

题解：P11777 [COTS 2013] 集合求解 / BOMBONI

什么啊，原来是结论题啊。

这道题我们看样例再手算几个样例，能够猜出，答案或许形式是 2^k-1。

我们通过猜出的结论来推理一下。首先，为什么要减 1，很容易猜到是排除了空集。其次，就要开始证明了。

我们先证明一个最基础的，就是通过补集和并集是可以得出交集的，证明如下：\complement_U(\complement_UA \cup \complement_UB)=A \cap B。

然后，我们发现，如果我们将元素分个块（如果两个元素所在的所有集合都是一样的，就合并），然后我们通过若干个操作，发现我们如何都不能拆分这个块（你可以试试哦），我们求出这些块的个数，再带入我们猜测的公式，却发现答案一模一样，为何？

我们很容易知道，如果有一个块，我们将这个元素所在的所有集合取交集，最终结果就是这个块，这很容易想到了，所以我们取交集后的最小单位就是这些块，所以最终简化为了我们取不取这个块，也就是两个选择，于是排除掉空集答案就是 2^k-1（k 为块的个数）。

那块的个数怎么求？我们注意到 1\le M \le 50 我们可以使用二进制存储，再去重即可咩。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+101;
const int mod=1e9+9;
long long q[N];
long long powd(long long x){
    if(!x){
        return 1;
    }
    if(x==1){
        return 2;
    }
    if(x%2==0){
        long long y=powd(x/2)%mod;
        return y*y%mod;
    }else{
        return powd(x-1)*2%mod;
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int len;
        scanf("%d",&len);
        long long k=0;
        for(int j=1;j<=len;j++){
            int x;
            scanf("%d",&x);
            q[x]|=(1ll<<i);
        }
    }
    sort(q+1,q+n+1);
    int k=unique(q+1,q+n+1)-q-1;
    printf("%lld\n",((powd(k)-1)%mod+mod)%mod);
    return 0;
}