【题解】BZOJ 2839 集合计数

请注意,本文编写于 97 天前,最后修改于 97 天前,其中某些信息可能已经过时。

Problem

求 $n$ 个不同元素的的子集中任取若干个使得交集元素个数为 $k$ 的方案数

Thought

设 $F[k]$ 表示确定大小为 $k$ 的交集后其他的任选的方案数

$$ F[k]={n\choose k}(2^{2^{n-k}}-1) $$

设 $f[k]$ 表示交集元素个数恰好为 $k$ 的方案数

对于每一个交集 $S$ ,其对 $f[|S|]$ 的贡献为其他位置均不能相同的方案
对于每一个交集 $S$ ,其对 $F[|S|]$ 的贡献为其他位置任选的方案

可以发现,对于包含了 $S$ 这个集合作为子集的任意的 $f[S']$ ,它们的贡献总和恰巧是 $S$ 对 $F[|S|]$ 的贡献

那么,对于所有的任意集合 $S$ ,都有 $val(S)=\sum_{S\subseteq S'}f[|S'|]$ ,而 $F[|S|]=\sum_{S}val(S)$

如果直接将 $f$ 和 $F$ 建立关系,恰好可以写为:

$$ F(|S|)=\sum_{S'}{|S'|\choose|S|}f(|S'|) $$

简单来说:

$$ F(k)=\sum_{i=0}^{n}{i\choose k}f(i) $$

利用二项式反演可得:

$$ f(k)=\sum_{i=0}^{n}(-1)^{|k-i|}{i\choose k}F(i) $$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1000010;
const int mod = 1000000007;
int n, k;
int inv[N], invPro[N];
int fac[N];

int F[N];

void prepare() {
    inv[0] = invPro[0] = fac[0] = 1;
    inv[1] = invPro[1] = fac[1] = 1;
    for(int i = 2; i < N; ++ i) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        invPro[i] = 1ll * invPro[i - 1] * inv[i] % mod;
        fac[i] = 1ll * fac[i - 1] * i % mod;;
    }
}
int C(int n, int m) {
    if(n < m) return 0;
    return 1ll * fac[n] * invPro[m] % mod * invPro[n - m] % mod;
}
int qpow(int a, int b, int mod) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    n = read(); k = read();
    prepare();
    for(int i = 0; i <= n; ++ i)
        F[i] = 1ll * C(n, i) * (qpow(2, qpow(2, n - i, mod - 1), mod) - 1 + mod) % mod;
    int ans = 0;
    for(int i = k; i <= n; ++ i) {
        if((k - i) % 2) {
            ans -= 1ll * C(i, k) * F[i] % mod;
            while(ans < 0) ans += mod; 
        }
        else {
            ans += 1ll * C(i, k) * F[i] % mod;
            while(ans >= mod) ans -= mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论