首页 > 题解 > bzoj 2839 集合计数

bzoj 2839 集合计数

Description

一个有N个元素的集合有2^N个不同子集(包含空集),现在要在这2^N个集合中取出若干集合(至少一个),使得它们的交集的元素个数为K,求取法的方案数,答案模1000000007。(是质数喔~)

Input

一行两个整数N,K

Output

一行为答案。

Sample Input

3 2

Sample Output

6

HINT

【样例说明】

假设原集合为{A,B,C}

则满足条件的方案为:{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

【数据说明】

对于100%的数据,1≤N≤1000000;0≤K≤N;

题解

首先固定$k$个元素作为交集,那么方案就是$k\choose n$

剩下了$2^{n – k}$个集合,那么就可以选剩下的:

$${1\choose 2^{n – k}}+{2\choose 2^{n – k}}+\cdots +{2^{n – k} \choose 2^{n – k}} = 2^{2^{n – k}}$$

但是这样选出来的有可能有不合法的,交集大小可能大于k,那就要容斥了。

设$f(k) = {k \choose n} \times 2^{2^{n – k}}$

那么答案应该为

$$f(k) \times { k\choose k} – f(k+1) \times { k\choose k+1} + f(k+2) \times { k\choose k+2} \cdots f(n) \times {k \choose n}$$

因为第一项即使不考虑交集大小可以大于k的情况,也会多出来很多重复的情况,因为选取的k个元素和选取的集合可能是重复的。那么后面进行容斥的时候就要利用组合数将重复的去掉

对求$2^{2^{n – k}}$,百度扩展欧拉定理应该就行


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×