[COCI2011-2012#6] KOŠARE

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;
}