SP13106 KOSARE - KOSARE
_Arahc_
·
·
题解
子集反演例题，这里补充一下子集反演的式子吧：
\text{let }F_S=\sum_{T\subset S} G_T
\text{then }G_S=\sum_{T\subset S} (-1)^{\left|S-T\right|} F_T
可以用 FWT 实现。
题目大意
题目传送门：Link to Luogu。
给定 n 个集合，全集共有 m 个元素。求选择一些集合使其并起来是全集的方案数。
题目分析
但是状压 DP 貌似很难实现？
设 $f_S$ 表示集合为 $S$ **的子集**的集合个数。那么 $f_S$ 是可以直接高维前缀和求出来的，FWT 或一下即可。
考虑 $f_S$ 和答案有什么关系？
设 $F_S$ 表示选择的集合的并集为 $S$ **的子集**的方案数，那么只要这个集合是 $S$ 的子集，就可以选（也可以不选，要记得去掉都不选的情况），因此 $F_S=2^{f_S}-1$。
要求的是选择的集合的并集恰好为集合 $S$ 的方案数，子集反演一下即可。
复杂度 $\mathcal O(m\times 2^m+n)$。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=2000006,mod=1000000007;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
int res=1;
while(p){
if(p&1) res*=a,res%=mod;
a*=a,a%=mod,p>>=1;
}
return res;
}
int n,m,S,f[max_n],F[max_n],ans;
inline void OR(int *f,int x=1){
for(register int k=1,l=2;l<=S;l<<=1,k<<=1)
for(register int i=0;i<S;i+=l)
for(register int j=0;j<k;++j)
f[i+j+k]+=f[i+j]*x%mod,
f[i+j+k]=(f[i+j+k]+mod)%mod;
}
signed main(){
n=read(),m=read(),S=(1<<m);
for(register int i=1;i<=n;++i){
int k=read(),st=0;
for(register int i=1;i<=k;++i){
int p=read()-1;
st|=(1<<p);
}
++f[st];
}
OR(f);
for(register int i=0;i<S;++i)
F[i]=mi(2,f[i])-1;
OR(F,-1);
write(F[S-1]);
return 0;
}
```