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；

题解

bzoj题目链接（权限题）

前置知识：广义容斥原理

考虑对于每个方案作为一个元素，每一位相同作为一个性质。

考虑在\(n\)个里选\(x\)个，要满足这\(x\)个性质，即集合中有\(x\)个相同，剩下\(n-x\)个集合里的元素可选可不选，但是不能都不选，要减去空集的一个，注意这里的集合指的是题目中的集合，

所以可得：

\[\alpha (x) = \binom{n}{x} (2^{2^{n-x}}-1)
\]

然后设\(\beta (x)\)为恰好有x个性质的元素个数，可得：

\[\beta(x) = \sum _{i=x} ^{n} (-1)^{i-x}\binom{i}{x} \alpha(i)
\]

答案为\(\beta (k)\)。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) x=-x,putchar('-');

    if(!x) return ;print(x/10),putchar(x%10+'0');

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define maxn 1000050

#define mod 1000000007

int n,fac[maxn],ifac[maxn],f[maxn],k;

int qpow(int a,int x) {

    int res=1;

    for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod;

    return res;

}

signed main() {

    read(n),read(k);f[0]=2,fac[0]=ifac[0]=1;

    for(int i=1;i<=n;i++) f[i]=f[i-1]*f[i-1]%mod,fac[i]=fac[i-1]*i%mod;

    ifac[n]=qpow(fac[n],mod-2);

    for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;

    int ans=0;

    for(int op=-1,i=k;i<=n;i++) {

        op=-op;

        ans=(ans+op*fac[n]*ifac[i]%mod*ifac[n-i]%mod*(f[n-i]-1)%mod*fac[i]%mod*ifac[k]%mod*ifac[i-k]%mod)%mod;

    }

    write((ans%mod+mod)%mod);

    return 0;

}

巴特西

[bzoj2893] 集合计数