自动搬运

查看原文

来自洛谷，原作者为

	Aurelia_Veil 学术+全关私信|半退犇退TC半退谷|刷分号|必须蓝勾|目标估值325，目标等级分1500|六年级小学生初来乍到，互关私信咩|一只小dongdong，飞入花丛中~|不知道为什么运气很好的小dongdong

搬运于2025-08-24 23:10:10，当前版本为作者最后更新于2025-05-27 15:06:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：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;
}