【题解】KOSARE 容斥 SPOJ – KOSARE

题意（From Luogu）：

题目描述

现有 $N$ 个玩具箱，每个玩具箱里都有一些玩具，这些玩具编号为 $1 \dots M$ ，一种玩具可以在多个玩具箱中出现，但每个玩具箱中每种玩具最多只有一个。

现在求：从这些玩具箱中选出一部分使得每种玩具都有的方法数。由于答案很大很大所以 $\bmod 1\ 000\ 000\ 007$ 。

输入格式

第一行两个整数 $N,M$ 。

接下来 $N$ 行每行描述一个玩具箱，第一个整数 $K_i$ 表示这个玩具箱里有多少玩具，接下来 $K$ 个整数表示这个箱子里的玩具。

输出格式

一行一个整数，总的方法数 $\bmod 1\ 000\ 000\ 007$。

首先状压，用高维前缀和求出 $f[s]$表示 “玩具集合为 $s$的子集的箱子有多少个”

然后设 $g[s]$表示 “玩具集合为 $s$的子集的选择方式有多少种”，则 $g[s] = 2 ^ {f[s]}$

最后 $ans = \sum {(-1) ^ {|U – i|} g[i]}$

其中 $U$表示全集

代码：

#include <bits/stdc++.h>

#define NS (1000005)
#define MS (20)
#define MOD (1000000007)
#define lowbit(a) ((a) & (-(a)))
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) >= 0 ? (a) - (b) : (a) - (b) + MOD)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, cnt[1 << MS], Bin[NS], Bc[1 << MS], ans;

int main(int argc, char const* argv[])
{
    IN(n), IN(m), Bin[0] = 1;
    for (int i = 1; i <= n; i += 1)
        Bin[i] = pls(Bin[i - 1], Bin[i - 1]);
    for (int i = 1, a, s; i <= n; i += 1)
    {
        IN(a), s = 0;
        for (int j = 1, b; j <= a; j += 1) IN(b), s |= (1 << (b - 1));
        cnt[s]++;
    }
    for (int i = 0; i < m; i += 1)
        for (int j = 1; j < (1 << m); j += 1)
            if (j & (1 << i)) cnt[j] += cnt[j ^ (1 << i)];
    for (int i = 0; i < (1 << m); i += 1)
    {
        Bc[i] = Bc[i >> 1] + (i & 1);
        if ((m - Bc[i]) & 1) ans = mns(ans, mns(Bin[cnt[i]], 1));
        else ans = pls(ans, mns(Bin[cnt[i]], 1));
    }
    printf("%d\n", ans);
    return 0;
}