[bzoj 2839] 集合计数

bzoj 2839

思路

易得,答案为$$C_N^K\cdot \sum \limits_{i=0}^{N-K}\big((-1)^{N-K-i}\cdot C_{N-K}^i\cdot (2^{2^i}-1)\big)$$

代码

#include <iostream>
#include <cstdio>

const int MOD=1000000007;
int N, K, QwQ[1000010], inv[1000010], fac[1000010];

void pre(){
	QwQ[0]=2; fac[0]=inv[0]=fac[1]=inv[1]=1;
	for(int i=1; i<=N-K; i++) QwQ[i]=1LL*QwQ[i-1]*QwQ[i-1]%MOD;
	for(int i=2; i<=N; i++) inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
	for(int i=2; i<=N; i++) fac[i]=1LL*i*fac[i-1]%MOD;
	for(int i=2; i<=N; i++) inv[i]=1LL*inv[i]*inv[i-1]%MOD;
}

int C(int M, int N){return int(1LL*fac[M]*inv[N]%MOD*inv[M-N]%MOD);}

int main(){
	scanf("%d%d", &N, &K); pre(); int ans=0;
	for(int i=0; i<=N-K; i++)
		ans=(ans+1LL*(((N-K-i)&1)?-1:1)*C(N-K, i)*(QwQ[i]-1)%MOD)%MOD;
	ans=ans<0 ? ans+MOD : ans; printf("%d\n", int(1LL*ans*C(N, K)%MOD));
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注