传送门

最近搭$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);
}