自动搬运

查看原文

来自洛谷，原作者为

	UltiMadow Well I do.

搬运于2025-08-24 22:20:49，当前版本为作者最后更新于2020-08-29 16:51:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

update: 修正了几个明显的问题（

容斥 + sos dp

如果你不会 sos dp

首先发现 $m$ 很小，于是直接对于每一个箱子状压

于是问题转化为选若干个数使它们按位或为全集

继续转化一下，把每个箱子取个反，问题就变成了选若干个书使它们按位与为空集

接下来考虑 dp

$f_i$ 表示状态 $i$ 是多少个箱子状态的子集，$g_i$ 表示状态 $i$ 是多少种 箱子状态交集的子集，显然有 $g_i=2^{f_i}-1$，于是我们只需要计算 $f$

有方程：$f_i=\sum_{i\in j}a_j$，于是直接上 sos dp 即可

方程中 $a_j$ 表示状态 $j$ 和多少个箱子状态相等

注意这里与标准 sos dp 方程 $f_i=\sum_{j\in i}a_j$ 有区别，在实现的时候反一下就行了

计算出来 $f$ 和 $g$ 之后计算答案

答案要求按位与为空集，考虑容斥，全集即为 $g_0$

对于一个状态 $i$，若它有奇数个 1，则需要从答案里减去 $g_i$，否则就加上 $g_i$

于是这道题就被做完了，时间复杂度 $\mathcal O(2^mm)$

code:

#include<bits/stdc++.h>
#define MAXN 1<<23
#define p 1000000007
using namespace std;
int n,m,ans;
int f[MAXN],pw[MAXN];
int main(){
	pw[0]=1;
	for(int i=1;i<(1<<22);i++)pw[i]=(pw[i-1]+pw[i-1])%p;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int k;scanf("%d",&k);
		int st=(1<<m)-1;
		while(k--){
			int x;scanf("%d",&x);
			st^=(1<<(x-1));
		}f[st]++;
	}
	for(int i=1;i<=m;i++)
		for(int mask=0;mask<(1<<m);mask++)
			if(mask&(1<<(i-1)))
				f[mask^(1<<(i-1))]=(f[mask^(1<<(i-1))]+f[mask])%p;
	for(int mask=0;mask<(1<<m);mask++){
		int sgn=1;
		for(int i=1;i<=m;i++)
			sgn=(mask&(1<<(i-1)))?-sgn:sgn;
		ans=(ans+(pw[f[mask]]-1)*sgn)%p;
	}printf("%d",(ans+p)%p);
	return 0;
}