2839: 集合计数
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 883 Solved: 490
[Submit][Status][Discuss]
Description
一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得
它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）
Input
一行两个整数N,K
Output
一行为答案。
Sample Input
3 2
Sample Output
6
HINT
【样例说明】
假设原集合为{A,B,C}
则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}
【数据说明】
对于100%的数据，1≤N≤1000000；0≤K≤N；
Source
这若干个集合的交集的方案数：$C(n,k)$
那么问题就转化成：对剩下的$m=n-k$个数，求集合取法，使它们之间没有交集
这种计数问题一般用容斥瞎搞
先求出$m$个数构成的集合的所有取法：$2^{2^{m}}-1$
共$2^{m}$个集合，每个集合可取可不取$(2^{2^{m}}\; )$，再减去一个都不取的情况$(-1)$（试试n=k的情况）
蓝后我们把交集$>=1$的取法减掉：$-C(m,1)*(2^{2^{m-1}\; }-1)$
但是我们发现有多减了交集$>=2$的取法，于是再加回来$+C(m,2)*(2^{2^{m-2}\; }-1)$
...............
这就是容斥原理计数的基本套路辣
于是答案为$C(n,k)*\sum_{i=0}^{m=n-k}\; \; \; (-1)^i*C(m,i)*(2^{2^{m-i}}-1)$
后面这个$2^{2^{m-i}}$咋算呢
注意到$2^{2^m}\; =2^{2^{m-1}}\; *2^{2^{m-1}}\; $
于是我们倒着枚举$i$，每次统计完平方以下就好辣
注意别爆int了鸭TAT
#include<iostream>//注意防爆int
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 1000005
const ll P=;
int n,k,m;ll ans,nw,inv[N],fac[N],ifac[N];
inline ll C(int a,int b){return fac[a]*ifac[b]%P*ifac[a-b]%P;}
int main(){
scanf("%d%d",&n,&k);
inv[]=; fac[]=fac[]=ifac[]=ifac[]=;
for(int i=;i<=n;++i){
inv[i]=1ll*(P-P/i)*inv[P%i]%P;//乘法逆元线性预处理
fac[i]=fac[i-]*i%P;
ifac[i]=ifac[i-]*inv[i]%P;
}m=n-k;nw=;
for(int i=m;i>=;--i,nw=nw*nw%P)//倒着枚举i
ans=((ans+((i&)?-:)*C(m,i)%P*(nw-)%P)%P+P)%P;
ans=ans*C(n,k)%P;
printf("%lld",ans);
return ;
}