Problem
有 \(N\) 个箱子、\(M\) 种礼物，第 \(i\) 个箱子里有 \(K_i\) 种礼物。
需要选出一些箱子，要求每一种礼物至少出现在一个箱子中。
求可行的方案数 \(mod\) \(10^9 + 7\) 。
Input
输入第一行，包含正整数 \(N(1 \le N \le 10^6)\) 和 \(M(1 \le M \le 20)\) 。
接下来的 \(N\) 行中，每行包含一个整数 \(K_i(0 \le K_i \le M)\) 和 \(K_i\) 个在 \([1,M]\) 范围内的整数，表示箱子里包含的礼物。
Output
输出仅一行，包含方案数 \(mod\) \(10^9+7\).
Sample
Input 1
3 3
3 1 2 3
3 1 2 3
3 1 2 3
Output 1
7
Input 2
3 3
1 1
1 2
1 3
Output 2
1
Input 3
4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5
Output 3
6
Solution
不难看出，这是一道容斥题。同时观察到 \(M\) 较小，可以状压。
定义 \(f_i\) 表示至少不选状态为 \(i\) 的礼物的方案数，可以在读入的时候累计，然后做一遍前缀和得到。
最后做一个容斥，得到最后的结果。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int kmax = 1e6 + 3;
const int kmaxM = 23;
const int Mod = 1e9 + 7;
int n, m;
int num[kmax][kmaxM], numc[kmax];
long long f[1 << kmaxM];
long long res;
long long p[kmax];
int main() {
cin >> n >> m;
for (int i = 1, k; i <= n; i++) {
cin >> k;
int tot = 0;
for (int j = 1, x; j <= k; j++) {
cin >> x;
tot |= 1ll << (x - 1); // 排除
}
f[((1 << m) - 1) ^ tot]++;
}
for (int i = 0; i < m; i++) { // 前缀
for (int j = 0; j < 1 << m; j++) {
if (j & (1 << i)) {
f[j ^ (1 << i)] = (f[j ^ (1 << i)] + f[j]) % Mod;
}
}
}
p[0] = 1;
for (int i = 1; i < kmax; i++) { // 预处理2的次方
p[i] = p[i - 1] * 2 % Mod;
}
res = p[n];
for (int i = 1; i < 1 << m; i++) {
int tot = __builtin_popcount(i);
tot = (tot & 1 ? -1 : 1); // 容斥
res = (res + tot * p[f[i]] % Mod + Mod) % Mod;
}
cout << res;
return 0;
}