题解 P6442 【[COCI2011-2012#6] KOŠARE】

· · 题解

update: 修正了几个明显的问题（

容斥 + sos dp

如果你不会 sos dp

首先发现 m 很小，于是直接对于每一个箱子状压

于是问题转化为选若干个数使它们按位或为全集

继续转化一下，把每个箱子取个反，问题就变成了选若干个书使它们按位与为空集

接下来考虑 dp

f_i$ 表示状态 $i$ 是多少个箱子状态的子集，$g_i$ 表示状态 $i$ 是多少种 箱子状态交集的子集，显然有 $g_i=2^{f_i}-1$，于是我们只需要计算 $f

有方程：f_i=\sum_{i\in j}a_j，于是直接上 sos dp 即可

方程中 a_j 表示状态 j 和多少个箱子状态相等

注意这里与标准 sos dp 方程 f_i=\sum_{j\in i}a_j 有区别，在实现的时候反一下就行了

计算出来 f 和 g 之后计算答案

答案要求按位与为空集，考虑容斥，全集即为 g_0

对于一个状态 i，若它有奇数个 1，则需要从答案里减去 g_i，否则就加上 g_i

于是这道题就被做完了，时间复杂度 \mathcal O(2^mm)

code:

#include<bits/stdc++.h>
#define MAXN 1<<23
#define p 1000000007
using namespace std;
int n,m,ans;
int f[MAXN],pw[MAXN];
int main(){
    pw[0]=1;
    for(int i=1;i<(1<<22);i++)pw[i]=(pw[i-1]+pw[i-1])%p;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int k;scanf("%d",&k);
        int st=(1<<m)-1;
        while(k--){
            int x;scanf("%d",&x);
            st^=(1<<(x-1));
        }f[st]++;
    }
    for(int i=1;i<=m;i++)
        for(int mask=0;mask<(1<<m);mask++)
            if(mask&(1<<(i-1)))
                f[mask^(1<<(i-1))]=(f[mask^(1<<(i-1))]+f[mask])%p;
    for(int mask=0;mask<(1<<m);mask++){
        int sgn=1;
        for(int i=1;i<=m;i++)
            sgn=(mask&(1<<(i-1)))?-sgn:sgn;
        ans=(ans+(pw[f[mask]]-1)*sgn)%p;
    }printf("%d",(ans+p)%p);
    return 0;
}