BZOJ 2339 【组合数学/递推】

HNOI2011 卡农

卡农折磨了我整个童年,没想到长大后还要被他折磨。

[Description]

给定n,m,求要在n个元素的所有$2^n-1$子集(除了空集)的选m个不同的集合,且任意元素出现的次数为偶数,问有几种取法。

[Hint]

$n,m≤10^6$,答案对$100000007$取模。

[Solution]

day2的压轴题…
其实看完题解觉得挺简单,但就是想不到啊!!!一直在想组合数学组合数学,根本没有往递推方向去考虑,果然还是学得太死了。
答案要求是无序的,但有序的好算一些,算出来再乘个m!的逆元就可以了。
设$f[i]$表示取满足题意的i个集合有多少种合法方案。
我们知道,当前i-1个集合确定时,第i个集合是也是确定了的。
根据乘法原理,取i-1个集合的方案共有$(2^{n}-1)×(2^{n}-2)…×(2^{n}-i+1)$种。
我们需要减去不合法的方案,分为以下两种:
1.前i-1个集合已经合法
这样,无论加进的第i个子集是什么,都是不合法的,贡献为$f[i-1]$。
2.第i个子集与前面某一个重复
与第i个子集重复的集合的位置有$i-1$种可能,重复的子集种数可能有$2^{n}-1-(i-2)$种,其他合法元素的可能的排列有$f[i-2]$种,根据乘法原理,贡献为$(i-1)×f[i-2]×2^{n}-1-(i-2)$
所以递推式为$$f[x]=[\prod_{i=1}^{x-1}(2^n-i)]-f[x-1]-f[x-2]×(i-1)×(2^{n}-1-(i-2))$$
取模取得我都晕了。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>

typedef long long ll;
const int mod=100000007;
const int maxn=1000001;
int f[maxn],g[maxn]={1},fac=1;

int pow(int a,int n){
int res=1;
while(n){
if(n&1) res=(ll)res*a%mod;
a=(ll)a*a%mod,n>>=1;
}
return res;
}

int main(){
int n,m; scanf("%d%d",&n,&m);
int bin=pow(2,n);
for(int i=1;i<=m;i++) g[i]=(ll)g[i-1]*(bin-i+mod)%mod,fac=(ll)fac*i%mod;
for(int i=3;i<=m;i++){
f[i]=(g[i-1]-f[i-1]+mod)%mod;
f[i]=(f[i]-(ll)f[i-2]*(i-1)%mod*(bin-i+1)%mod+mod)%mod;
}
int ans=(ll)f[m]*pow(fac,mod-2)%mod;
printf("%d",ans);
return 0;
}