2803번: KOŠARE

https://www.acmicpc.net/problem/2803

$O(m(n+2^m))$

풀이:
http://hsin.hr/coci/archive/2011_2012/contest6_solutions.zip
6번 참조

#include<cstdio>
#define mod int(1e9+7)
int n, m, r;
long long c[1 << 20];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1 << m; i--;) c[i]++;
    while (n--) {
        int k, x, tot = 0;
        for (scanf("%d", &k); k--;) {
            scanf("%d", &x);
            tot += 1 << x - 1;
        }
        c[tot] = c[tot] * 2 % mod;
    }
    for (int i = 1; i < 1 << m; i *= 2)
        for (int j = 1 << m; j--;) if (i&j) c[j] = c[j] * c[j^i] % mod;
    for (int i = 1 << m; i--;) {
        int b = 0;
        for (int j = i; j; j &= j - 1) b++;
        r = (r + mod + c[i] * (m - b & 1 ? -1 : 1)) % mod;
    }
    printf("%d", r);
    return 0;
}