bzoj 2839 集合计数

题目描述

https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-2839

简要题意：现在有一个含有 $n$ 个元素的集合，我们要从这个集合中所有 $2^n$ 个子集中选出若干个，使得他们的交集元素个数为 $k$，求有多少种选法

$n\le 10^6$

Solution

我们考虑容斥，令 $f_k=\sum_{i=k}^n \binom{i}{k}g_i$，其中 $g_k$ 为交集的元素个数恰好为 $k$ 的方案数，则答案为 $g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_k$

容易得到 $f_k=\binom{n}{k}2^{2^{n-k}}$

#include <iostream>
#include <cstdio>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n, int p = 1000000007) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s; 
}

ll fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; } 

int n, k;

ll f[maxn], ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; init_C(n); 
    for (int i = k; i <= n; ++i) f[i] = C(n, i) * pow_mod(2, pow_mod(2, n - i, p - 1)) % p;
    for (int i = k, t = 1; i <= n; ++i, t = -t) ans = (ans + t * C(i, k) * f[i]) % p;
    cout << (ans + p) % p << "\n"; 
    return 0;
}