卡农折磨了我整个童年，没想到长大后还要被他折磨。
[Description]
给定n,m，求要在n个元素的所有2n−1子集（除了空集）的选m个不同的集合，且任意元素出现的次数为偶数，问有几种取法。
[Hint]
n,m≤106,答案对100000007取模。
[Solution]
day2的压轴题…
其实看完题解觉得挺简单，但就是想不到啊！！！一直在想组合数学组合数学，根本没有往递推方向去考虑，果然还是学得太死了。
答案要求是无序的，但有序的好算一些，算出来再乘个m!的逆元就可以了。
设f[i]表示取满足题意的i个集合有多少种合法方案。
我们知道，当前i-1个集合确定时，第i个集合是也是确定了的。
根据乘法原理，取i-1个集合的方案共有(2n−1)×(2n−2)…×(2n−i+1)种。
我们需要减去不合法的方案，分为以下两种：
1.前i-1个集合已经合法
这样，无论加进的第i个子集是什么，都是不合法的，贡献为f[i−1]。
2.第i个子集与前面某一个重复
与第i个子集重复的集合的位置有i−1种可能，重复的子集种数可能有2n−1−(i−2)种，其他合法元素的可能的排列有f[i−2]种，根据乘法原理，贡献为(i−1)×f[i−2]×2n−1−(i−2)
所以递推式为
f[x]=[i=1∏x−1(2n−i)]−f[x−1]−f[x−2]×(i−1)×(2n−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;
}
|
