BZOJ 2839 集合计数

发表于 | 分类于

Description

对于一个\(n\)个元素集合的所有子集，我们要从这些子集中取出至少一个，使得取出的集合的交的大小恰好为\(k\)。求方案数，答案对\(10^9+7\)取模。

\(1\leq n\leq 10^6, 0\leq k\leq n\)。

Solution

恰好\(k\)个元素并不好求，但是至少\(k\)个元素是可做的。答案显然是\(\binom{n}{k}(2^{2^{n - k}} - 1)\)（注意这个东西的话如果交集大小为\(s > k\)的话一个集合集的贡献会算\(\binom{s}{k}\)次，也就是先规定交集再考虑方案数，下面还要用这个性质）。

假设恰好\(k\)个的方案数为\(a_k\)，上述至少\(k\)个的方案数为\(b_k\)。那么有： \[ b_k = \sum_{i = k}^n \binom{i}{k}a_i \] 这就是广义容斥原理的标准形式……反推一下可以得到： \[ a_k = \sum_{i = k}^n (-1)^{i - k}\binom{i}{k}b_i \] 然后就做完力，，，

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
typedef long long ll;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b, ll p = ha) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % p;
    res = res * res % p; b >>= 1;
  }
  return ans;
}

const int maxn = 1000005;
ll fac[maxn], ifac[maxn];
void process() {
  int n = 1000000;
  fac[0] = 1;
  for(int i = 1; i <= n; i ++) {
    fac[i] = (ll)i * fac[i - 1] % ha;
  }
  ifac[n] = pow_mod(fac[n], ha - 2LL);
  for(int i = n - 1; i >= 0; i --) {
    ifac[i] = (ll(i + 1)) * ifac[i + 1] % ha;
  }
}
ll C(int n, int m) {
  ll ret = fac[n] * ifac[n - m] % ha;
  ret = ret * ifac[m] % ha;
  return ret;
}

int main() {
  process();
  int n, k; scanf("%d%d", &n, &k);
  ll ans = 0;
  for(int i = k; i <= n; i ++) {
    ll delta = C(n, i);
    ll xi = (pow_mod(2, pow_mod(2, n - i, ha - 1LL)) - 1LL + ha) % ha;
    delta = delta * xi % ha;
    delta = delta * C(i, k) % ha;
    if(1 & (i - k)) delta = (ha - delta);
    ans += delta;
    if(ans >= ha) ans -= ha;
  }
  printf("%lld\n", ans);
  return 0;
}