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}}$，百度扩展欧拉定理应该就行

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6+5, mod = 1e9+7;
int n, k;
long long ans, now = 2, inv[N], fac[N], facInv[N];
inline long long C(int n, int m) { return fac[n] * facInv[m] % mod * facInv[n - m] % mod; }
int main() {
    scanf("%d%d", &n, &k);
    inv[1] = fac[0] = facInv[0] = 1;
    for(int i = 1; i <= n; i++) {
        if (i != 1) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        fac[i] = fac[i - 1] * i % mod;
        facInv[i] = facInv[i - 1] * inv[i] % mod;
    }
    n -= k;
    for(int i = n; i >= 0; i--) {
        (ans += ((i & 1) ? -1 : 1) * C(n, i) * (now - 1) % mod) %= mod;
        now = now * now % mod;
    }
    if (ans < mod) ans += mod;
    ans = ans * C(n + k, k) % mod;
    printf("%lld\n", ans);
}