SP13106 KOSARE

Arahc 11.0

题面

简化题意

给定 nn 个集合,全集有 mm 个元素。求选择一些集合使其并为全集的方案数。

n106,m20n\leq 10^6,m\leq 20

题解

mm 的数据范围很小,从这里入手,考虑状压。

但是状压 DP 貌似很难实现?

fSf_S 表示集合为 SS 的子集的集合个数。那么 fSf_S 是可以直接高维前缀和求出来的,FWT 或一下即可。

考虑 fSf_S 和答案有什么关系?

FSF_S 表示选择的集合的并集为 SS 的子集的方案数,那么只要这个集合是 SS 的子集,就可以选(也可以不选,要记得去掉都不选的情况),因此 FS=2fS1F_S=2^{f_S}-1

要求的是选择的集合的并集恰好为集合 SS 的方案数,子集反演一下即可。

复杂度 O(m×2m+n)\mathcal O(m\times 2^m+n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}
  • 标题: SP13106 KOSARE
  • 作者: Arahc
  • 创建于 : 2022-02-08 08:00:00
  • 更新于 : 2023-03-15 11:41:52
  • 链接: https://arahc.github.io/2022/02/08/【题解】SP13106-KOSARE/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
SP13106 KOSARE