2020-2021:teams:legal_string:jxm2001:二项式反演
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
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> | ||
2020-2021/teams/legal_string/jxm2001/二项式反演.1597976976.txt.gz · 最后更改: 2020/08/21 10:29 由 jxm2001
