题目链接
解析
题目等价于给定 \(n\) 个集合，求选出来的集合的并等于全集的方案数。
考虑容斥。记 \(P_i\) 表示第 \(i\) 个元素在最终集合里的选法，那么要求即为 \(\left| \bigcap_{i=1}^{m}P_i\right|\)。记 \(Q_i\) 表示第 \(i\) 个元素不在最终集合里的选法，那么有 \(\left| \bigcap_{i=1}^{m}P_i\right|=\left| U\right| - \left| \bigcup_{i=1}^{m}Q_i\right|\)，其中 $ \left| \bigcup_{i=1}^{m}Q_i\right|$ 代表至少有一个元素不在最终集合里的选法个数, \(U\) 为全集
问题变为求 $ \left| \bigcup_{i=1}^{m}Q_i\right|$。由容斥原理，我们有：
\[\left| \bigcup_{i=1}^{m}Q_i\right| =\sum_{\emptyset \not=S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert - 1}\left| \bigcap_{j\in S}Q_j\right|
\]
设 \(f_S=\left| \bigcap_{j\in S} Q_j\right|\) 表示选出来的集合并中不含 \(S\) 中元素的方案数。并中不含 \(S\) 中元素又意味着补集的交中含有所有 \(S\) 中元素。设 \(g_S\) 表示补集中含有所有 \(S\) 中元素的集合个数，那么 \(f_S = 2^{g_S}\)。
对于 \(g_S\)，有 \(g_S=\sum_{S\subseteq T} h_T\)，其中 \(h_T\) 表示补集为 \(T\) 的集合个数。使用 SOSDP 求解，时间复杂度 \(O(m2^m)\)。
事实上，我们有 \(\bigcap_{i \in \emptyset}Q_i=U\)，可以理解为限制集合为空所以没有任何限制，所以：
\[\sum_{\emptyset \not=S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert - 1}\left| \bigcap_{j\in S}Q_j\right|=\sum_{S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert - 1}\left| \bigcap_{j\in S}Q_j\right|+\left| U \right|
\]
于是：
\[\begin{aligned}
\left| U\right| - \left| \bigcup_{i=1}^{m}Q_i\right| &= \left| U\right| - (\sum_{S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert - 1}\left| \bigcap_{j\in S}Q_j\right|+\left| U \right|)\\
&=- (\sum_{S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert - 1}\left| \bigcap_{j\in S}Q_j\right|)\\
&= \sum_{S \subseteq [1,m]\cap \mathbb{Z}}(-1)^{\lvert S\rvert}\left| \bigcap_{j\in S}Q_j\right|
\end{aligned}
\]
由此可以衍生出不同的实现方法。
代码
/*
此代码根据最后推出的式子实现。
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
//#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef unsigned ui;
typedef pair<int,int> pii;
const int N = (1 << 20) + 5,M = 15,P = 2000000,mod = 1e9 + 7,mod2 = 1e9 + 7,b1 = 131,b2 = 13331;
int f[N],g[N];
int mi2[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);mi2[0] = 1;for(int i=1;i<N;i++){mi2[i] = mi2[i - 1] * 2ll % mod;}int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int k;cin>>k;int y = (1 << m) - 1;for(int j=1;j<=k;j++){int x;cin>>x;x--;y ^= (1 << x);}g[y]++;}for(int i=0;i<m;i++){for(int j=0;j<(1 << m);j++){if(!(j & (1 << i))){g[j] += g[j ^ (1 << i)];}}}int res = 0;for(int i=0;i<(1 << m);i++){f[i] = mi2[g[i]];int p = __builtin_popcount(i) % 2 == 0 ? 1 : -1;res = (res + mod + 1ll * p * f[i]) % mod;}cout<<res;return 0;
}