Jzoj3170 挑选玩具

ABC找到N个箱子,箱子里装着一些玩具,一共有M种玩具,编号从1到M,同一种玩具可能出现在多个箱子里。

ABC决定从中选择一些箱子,把这些箱子中的玩具聚集到一起,必须保证每种玩具至少出现一次。

问ABC一共有多少种选择方案 (1<=N<=1,000,000,1<=M<=20)

第三次看到这个题了,前两次都忘了怎么做了。。。

好的第一眼看上去可以dp做,结果发现只能过50%数据

矩阵明显不可做,让后开始考虑数学方法

考虑容斥原理,我们发现可以用总方案减去至少不出现一种玩具的方案数

令f(S)表示选出的方案中,所有元素都在S中的方案数(但是不要求S每个元素都要出现)

令g(S)表示选出的方案中,不包含任何一个S含有的元素的方案数

那么可以得到Answer=2^N-Σg(S)*(-1)^|S|,g(S)=f(~S)

现在考虑如何快速计算f

我们发现如果对于每个S都求出有几个给出的集合x满足x∩S=x就可以快速计算得到f(S)=2^x-1

而我们发现,f(S)一定被包含于f(S∪M)

所以可以运用分治法来解决:f[x+m]+=f[x]

最后直接统计即可

#pragma GCC opitmize("O3") #pragma G++ opitmize("O3") #include<stdio.h> #include<string.h> #include<algorithm> #define N (1<<m) #define M 1000000007 using namespace std; int c[1<<20],w[1<<20],f[1<<20],p[1<<20]={1},n,m,S=0; void cdq(int l,int r){ if(l==r){ f[l]=c[l]; return ; } int m=l+r>>1; cdq(l,m); cdq(m+1,r); for(int i=l;i<=m;++i) f[i+m-l+1]+=f[i]; } int main(){ scanf("%d%d",&n,&m); for(int x,y,z,i=1;i<=n;++i){ for(z=0,scanf("%d",&x);x--;z+=1<<y-1) scanf("%d",&y); ++c[z]; } for(int i=1;i<N;++i) w[i]=w[i>>1]^(i&1); for(int i=1;i<=n;++i) p[i]=(p[i-1]<<1)%M; cdq(0,N-1); for(int i=0;i<N;++i) S=w[i]?(S-p[f[N-i-1]]+1)%M:(S+p[f[N-i-1]]-1)%M; printf("%d",(S+M)%M); }
相关文章
相关标签/搜索