BZOJ2839 集合计数

Description

从大小为 $n$ 的集合中取出若干子集（至少一个），使得它们的交集的元素个数为 $K$ ，求取法的方案数，答案模$1000000007$

Solution

$ans$ = 先选出这 $k$ 个元素是哪些 * 让剩下的交集为空

让剩下的交集为空 =(容斥) 随便选 - 交集至少一个元素 + 交集至少两个元素 …

交集至少为 $i$ 的方案数是 $\binom{n-k}{i} \cdot (2^{2^{n-k-i}}-1)$ (从剩下的 $n - k$ 里选 $i$ 个 * (有这些元素的子集随便选 - 啥都不选的一组)

$$ans = \binom{n}{k}\sum\limits_{i=0}^{n-k}(-1)^i \binom{n-k}{i}\cdot (2^{2^{n-k-i}}-1)$$

Code

/**
 * Author: AcFunction
 * Date:   2019-03-04 17:33:39
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

const int N = 1000005;
const ll mod = (ll)1e9 + 7;  

ll fac[N], ans; 

ll fpw(ll x, ll k, ll p) {
  ll ret = 1ll; 
  while(k) {
    if(k & 1) ret = ret * x % p; 
    x = x * x % p; k >>= 1; 
  } return ret; 
}

void prework(int n) {
  fac[0] = fac[1] = 1; 
  rep(i, 2, n) fac[i] = fac[i - 1] * i % mod; 
}

ll C(int n, int m) {
  if(m > n) return 0; 
  else return fac[n] * fpw(fac[n - m], mod - 2, mod) % mod * 
              fpw(fac[m], mod - 2, mod) % mod; 
}

int main() {
  INIT(); 
  int n, k; cin >> n >> k; prework(n); 
  ll pw1 = ((n - k) & 1) ? -1 : 1, pw2 = 2; 
  per(i, n - k, 0) {
    ans += pw1 * (pw2 - 1) % mod * C(n - k, i) % mod;
    ans %= mod; pw1 *= -1; pw2 *= pw2; pw2 %= mod;  
  } ans = ans * C(n, k) % mod; ans = (ans + mod) % mod; 
  cout << ans << endl;  
  return 0; 
}