bzoj 2839 集合计数

传送门

最近搭$blog$导致极度颓废。。。

权限题，简述一下题意：

在有$n(n\le 1e6)$个元素的所有子集（包含空集）中选出若干个，有多少种选法使它们交集大小恰好为$k(k\le n)$？

设$f(n)$表示在有$n$个元素的集合中取若干个子集，它们交集为空的方案数。

再设$g(n)$表示在有$n$个元素的集合中取任意个子集的方案数，显然$g(n)=2^{2^n}$。

考虑把$g(n)$分类，把交集大小相同的分到一起，就有$g(n)=\sum\limits_{i=0}^nC_n^{n-i}f(i)=\sum\limits_{i=0}^nC_n^if(i)$

上二项式定理：$f(n)=\sum\limits_{i=0}^n(-1)^{n-i}C_n^ig(i)$

答案就是$C_n^kf(n-k)$

对于$g$，有$g(0)=2,g(n)=2^{2^n}=2^{2^{n-1}+2^{n-1}}=2^{2^{n-1}}2^{2^{n-1}}=g(n-1)g(n-1)$，就能$O(n)$预处理了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1000005
#define inf 0x3f3f3f3f

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int fac[maxn]={1},inv[maxn],pow2[maxn]={2};
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
inline long long pow1(int x){
    return x&1?-1ll:1ll;
}
inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    int n=read(),k=read(),ans=0;
    for(register int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,pow2[i]=1ll*pow2[i-1]*pow2[i-1]%mod;
    inv[n]=INV(fac[n]);
    for(register int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(register int i=0;i<=n-k;++i)
        (ans+=pow1(n-k-i)*C(n-k,i)*pow2[i]%mod)%=mod;
    printf("%d\n",(1ll*C(n,k)*ans%mod+mod)%mod);
}