Warning: session_start(): open(/tmp/sess_ec9a946fb2b994f68928ef3d513dd0e7, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:二项式反演 [CVBB ACM Team]

用户工具

站点工具


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