bzoj2839

容斥原理+组合数学

看见这种恰有k个的题一般都是容斥原理，因为恰有的限制比较强，一般需要复杂度较高的方法枚举，而容斥就是转化为至少有k个，然后通过容斥原理解决

我们先选出k个元素作为交集，有C(n,k)种可能，那么剩下的n-k个元素既可以选也可以不选，一共有2^(n-k)种选法，每种选法对应了一个集合，也就是说一共有2^(n-k)种不同的集合，我们希望在这n-k个元素中选出若干个集合，使他们的交集为空，于是我们枚举选多少个元素，i=0->n-k,这样有C(n-k,i)种选法，然后我们使用容斥原理来计算i个元素交集为空集的集合数量，对于给定元素交集大小至少为i的情况，我们可以跟刚才一样先选出i个元素作为交集，方案数同上，然后方案数是2^(2^(n-i-k))-1，因为我们有2^(n-i-k)个集合，每个集合可以选或不选，因为已经选出i个元素作为交集，所以交集大小至少是i，其他的集合随便选就满足至少是i

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

using namespace std;

typedef long long ll;

const int N = , mod = ;

int n, k;

ll ans, pw = ;

ll inv[N], fac[N], facinv[N];

ll C(int n, int k)

{

    return fac[n] * facinv[k] % mod * facinv[n - k] % mod;

}

int main()

{

    scanf("%d%d", &n, &k);

    inv[] = inv[] = fac[] = fac[] = facinv[] = facinv[] = ;

    for(int i = ; i <= n; ++i)

    {

        fac[i] = fac[i - ] * (ll)i % mod;

        inv[i] = (mod - mod / i) * inv[mod % i] % mod;

        facinv[i] = facinv[i - ] * inv[i] % mod;

    }

    for(int i = n - k; i >= ; --i)

    {

        ans = (((ans + ((i & ) ? - : ) * C(n - k, i) * ((pw - ) % mod + mod) % mod) % mod) % mod + mod) % mod;

        pw = pw * pw % mod;

    }

    ans = ((ans * C(n, k) % mod) % mod + mod) % mod;

    printf("%lld\n", ans);

    return ;

}

巴特西

bzoj2839

最新文章

热门文章