两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:二项式反演 [2020/08/21 10:29] jxm2001 |
2020-2021:teams:legal_string:jxm2001:二项式反演 [2020/08/21 11:08] (当前版本) jxm2001 |
||
---|---|---|---|
行 13: | 行 13: | ||
===== 算法例题 ===== | ===== 算法例题 ===== | ||
- | ==== 题意 ==== | + | ==== 例题一 ==== |
+ | |||
+ | === 题意 === | ||
+ | |||
+ | 求错排数 $D_n$。 | ||
+ | |||
+ | === 题解 === | ||
+ | |||
+ | 考虑任意排列,有 $n!$ 种,其中恰有 $i$ 封信错排的方案数为 ${n\choose i}D_i$,于是 $n!=\sum_{i=0}^n{n\choose i}D_i$。 | ||
+ | |||
+ | 根据二项式反演,有 $D_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}i!$ | ||
+ | |||
+ | ==== 例题二 ==== | ||
+ | |||
+ | === 题意 === | ||
一个有 $n$ 个元素的集合,现在要从他的所有子集中取出至少一个集合,使得所选子集的交集的元素个数为 $k$,求方案数。 | 一个有 $n$ 个元素的集合,现在要从他的所有子集中取出至少一个集合,使得所选子集的交集的元素个数为 $k$,求方案数。 | ||
- | ==== 题解 ==== | + | === 题解 === |
定义 $f(k)$ 表示所有钦定 $k$ 个元素属于交集(其余元素任意)的方案数之和,于是有 $f(k)={n\choose k}2^{2^{n-k}}$。 | 定义 $f(k)$ 表示所有钦定 $k$ 个元素属于交集(其余元素任意)的方案数之和,于是有 $f(k)={n\choose k}2^{2^{n-k}}$。 | ||
行 96: | 行 110: | ||
<hidden 查看代码> | <hidden 查看代码> | ||
<code cpp> | <code cpp> | ||
+ | const int MAXN=2005,Mod=1e9+9; | ||
+ | int quick_pow(int a,int b){ | ||
+ | int ans=1; | ||
+ | while(b){ | ||
+ | if(b&1)ans=1LL*ans*a%Mod; | ||
+ | a=1LL*a*a%Mod; | ||
+ | b>>=1; | ||
+ | } | ||
+ | return ans; | ||
+ | } | ||
+ | int a[MAXN],b[MAXN],dp[MAXN][MAXN],frac[MAXN],invfrac[MAXN]; | ||
+ | int C(int a,int b){return 1LL*frac[a]*invfrac[b]%Mod*invfrac[a-b]%Mod;} | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(),k=read_int(),m; | ||
+ | if((n-k)&1){ | ||
+ | puts("0"); | ||
+ | return 0; | ||
+ | } | ||
+ | m=n+k>>1; | ||
+ | _rep(i,1,n)a[i]=read_int(); | ||
+ | _for(i,0,n)b[i]=read_int(); | ||
+ | sort(a+1,a+n+1);sort(b,b+n); | ||
+ | int pos=0; | ||
+ | dp[0][0]=1; | ||
+ | _rep(i,1,n){ | ||
+ | while(b[pos]<a[i]&&pos<n)pos++; | ||
+ | dp[i][0]=1; | ||
+ | _rep(j,1,i){ | ||
+ | if(j>pos)break; | ||
+ | dp[i][j]=(dp[i-1][j]+1LL*dp[i-1][j-1]*(pos+1-j))%Mod; | ||
+ | } | ||
+ | } | ||
+ | frac[0]=1; | ||
+ | _rep(i,1,n)frac[i]=1LL*frac[i-1]*i%Mod; | ||
+ | invfrac[n]=quick_pow(frac[n],Mod-2); | ||
+ | for(int i=n;i;i--)invfrac[i-1]=1LL*invfrac[i]*i%Mod; | ||
+ | int ans=0,t; | ||
+ | _rep(i,m,n){ | ||
+ | t=1LL*C(i,m)*frac[n-i]%Mod*dp[n][i]%Mod; | ||
+ | if((i-m)&1)ans=(ans-t)%Mod; | ||
+ | else ans=(ans+t)%Mod; | ||
+ | } | ||
+ | enter((ans+Mod)%Mod); | ||
+ | return 0; | ||
+ | } | ||
</code> | </code> | ||
</hidden> | </hidden> |