【BZOJ-2839】集合计数容斥原理 + 线性推逆元 + 排列组合

2022-03-05 13:10:18

2839: 集合计数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 229 Solved: 120
[Submit][Status][Discuss]

Description

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得

它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

Input

一行两个整数N,K

Output

一行为答案。

Sample Input

3 2

Sample Output

HINT

【样例说明】
假设原集合为{A,B,C}
则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

【数据说明】
对于100%的数据，1≤N≤1000000；0≤K≤N；

Source

Solution

先手推了N=2~3,K的值,又推了推式子,大体上有所发现

首先N个元素中交集出现i个元素的的方案数为$C^{i}_{n}$

那么剩下$2^{n-i}$个其他集合,任选的方案总数为$2^{2^{n-1}-1}$种

最后统计答案$\sum_{k<=i<=N}(-1)^{i-k}*C^{i}_{n}*C^{k}_{i}*(2^{2^{n-i}-1})$

数据范围明显不能直接预处理C,所以先预处理阶乘和逆元再计算C即可

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int N,K;

const long long p=1e9+;

#define maxn 1000010

long long inv[maxn],fac[maxn],ans;

void GetInv() {inv[]=;for (int i=; i<=N; i++) inv[i]=(p-p/i)*inv[p%i]%p;}

void Prework() {inv[]=;for (int i=; i<=N; i++)inv[i]=inv[i]*inv[i-]%p;}

void GetFac() {fac[]=;for (int i=; i<=N; i++) fac[i]=(long long)fac[i-]*i%p;}

long long C(long long n,long long m) {return fac[n]*inv[m]%p*inv[n-m]%p;}

int main()

{

    scanf("%d %d",&N,&K);

    GetFac(); GetInv(); Prework();

    for (long long i=N,tmp=; i>=K; i--,tmp=tmp*tmp%p)

        ans=(ans+((i-K&?p-:)*C(N,i)%p*C(i,K)%p*(tmp+p-)%p))%p;

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

    return ;

}

丧心病狂的压代码

码农公寓