题解：P10596 BZOJ2839 集合计数

Istruggle · 2024-12-12 18:17:29 · 题解

我们令 f_k 表示的交集的元素个数恰好为 k，令 g_k 表示的交集的元素个数至少为 k。根据二项式反演可得：

下面考虑如何求 g_k。

我们先钦定其中的 k 个元素为交集的元素，则方案数为 \binom{n}{k}，这表示在选出的集合中这 k 个元素一定选，这些钦定的集合还有 n-k 个元素可以选，枚举这 n-k 个元素选或不选共有 2^{n-k} 种方案，由于不能不选，所以 g_k = \binom{n}{k} ( 2^{2^{n-k}}-1)。最终答案为 f_k。

参考代码

#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7,N=1e6+5;
using namespace std;
int n,k,fac[N],inv[N];
int c(int a,int b){return fac[a]*inv[b]%mod*inv[a-b]%mod;}
int qpow(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1; 
    }
    return res;
}
int f[N],g[N];
signed main(){
    scanf("%lld%lld",&n,&k);
    fac[0]=1;
    for(int i = 1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2,mod);
    for(int i = n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i = 0;i<=n;i++)
    f[i]=c(n,i)*(qpow(2,qpow(2,n-i,mod-1),mod)-1)%mod;
    for(int i = k;i<=n;i++){
        int x;
        if((i-k)%2==1) x=-1;
        else x=1;
        int tmp=c(i,k)*f[i]%mod;
        tmp*=x; 
        g[k]=(g[k]+tmp+mod)%mod;
    }
    printf("%lld",g[k]);
}