二项式反演[bzoj3622]已经没有什么好害怕的了

前言

继续学习容斥的技巧！

题意简介

题面链接

题目大意

给出两个数组$a,b$
求有多少种对应方式使得有恰好$k$对匹配$(i,j)$满足ai>bja_i>b_jai​>bj​

数据范围

$n\le 2000,0\le k\le n$

题解

部分分

这道题的暴力是指数级的，对于这样的数据范围显得非常没有意义

正解

发现暴力的瓶颈在于枚举匹配的集合，那么说明我们不能直接枚举集合
考虑减少限制，使得计算变得简单，然后再把不满足的都扔掉，那么就能做出这道题，也就是容斥
我们先将两个数组分别排序，这样的话容易发现对于$a$中的一个元素aia_iai​，满足ai>bja_i>b_jai​>bj​的bjb_jbj​是$b$的一个前缀
定义$g[i]$为最大的下标$j$满足bj<aib_j<a_ibj​<ai​
定义$f[i][j]$表示$a$数组的前$i$个数，其中确定有$j$对匹配满足$a>b$（确定那么多，但不代表只有那么多），在这样的情况下这$j$对的选择方案数（这$j$对以外的数的匹配不同算同一种方案）
然后很容易贴出转移式子$$f[i][j+1]=f[i-1][j+1]+f[i-1][j]\ast (g[i]-j)$$
第一项代表当前这个数不匹配，第二项表示当前这个数匹配
设$F[i]=f[n][i]\ast (n-i)!$，那么$F[i]$就表示满足$a>b$的匹配对数大于等于$j$的对应方式数（注意，这个定义和上面的不同，乘一个阶乘后就所有数都固定了）
定义$Ans[i]$表示满足$a>b$的匹配对数等于$j$的对应方式数
容易发现$Ans[k]$即我们所要的答案
我们发现这样一个显然的式子F[k]=∑i=kn(ik)Ans[i]F[k]=\sum_{i=k}^n\binom{i}{k}Ans[i]F[k]=i=k∑n​(ki​)Ans[i]
注：(ij)=C(i,j)\binom{i}{j}=C(i,j)(ji​)=C(i,j)即组合数
二项式反演即可得Ans[k]=∑i=kn(−1)i−k(ik)F[i]Ans[k]=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}F[i]Ans[k]=i=k∑n​(−1)i−k(ki​)F[i]
那么什么是二项式反演呢？请看下一节
我们先把这题讲完，假设你推出了这个，那么就可以直接算答案了
前面$dp$的复杂度是Θ(n2)\Theta(n^2)Θ(n2)的，后面的答案计算由于只要算一个所以是$\Theta (n)$的
综上，总复杂度Θ(n2)\Theta(n^2)Θ(n2)

二项式反演

二项式反演的经典形式为fn=∑i=0n(−1)i(ni)gi⇔gn=∑i=0n(−1)i(ni)fif_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_ifn​=i=0∑n​(−1)i(in​)gi​⇔gn​=i=0∑n​(−1)i(in​)fi​
这篇博客用到的式子是另一个经典模型
fi=∑j=0i(n−jn−i)gj⇔gi=∑j=0i(−1)i−j(n−jn−i)fjf_i=\sum_{j=0}^i\binom{n-j}{n-i}g_j\Leftrightarrow g_i=\sum_{j=0}^i(-1)^{i-j}\binom{n-j}{n-i}f_jfi​=j=0∑i​(n−in−j​)gj​⇔gi​=j=0∑i​(−1)i−j(n−in−j​)fj​
应用的时候其实是进行了数组翻转和特殊值代换产生的
要问证明？请看我的另一篇总结博客

代码

东西讲完了，就可以安心写出前面的那一题了，贴上ac代码

#include
#include
#include
namespace fast_IO
{const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
#define rg register
typedef long long LL;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const LL mod=1000000009;
inline void md(LL&x){if(x>=mod)x-=mod;}
int n,k;
int a[2001],b[2001],g[2001];
inline LL pow(LL x,LL y)
{LL res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res;
}
LL fac[2001],inv[2001];
inline LL C(const LL x,const LL y)
{return fac[x]*inv[y]%mod*inv[x-y]%mod;}
LL f[2001],ans;
int main()
{read(n),read(k);if((n&1)!=(k&1)){print(0);return flush(),0;}k=(n-k)/2+k;for(rg int i=1;i<=n;i++)read(a[i]);for(rg int i=1;i<=n;i++)read(b[i]);std::sort(a+1,a+n+1);std::sort(b+1,b+n+1);for(rg int i=1,j=0;i<=n;i++){while(j<n&&b[j+1]<a[i])j++;g[i]=j;}fac[0]=1;for(rg int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=pow(fac[n],mod-2);for(rg int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;f[0]=1;for(rg int i=1;i<=n;i++)for(rg int j=n-1;j>=0;j--)md(f[j+1]+=f[j]*(g[i]-j)%mod);for(rg int i=k,j=1;i<=n;i++,j^=1){if(j)ans+=f[i]*C(i,k)%mod*fac[n-i]%mod;else ans-=f[i]*C(i,k)%mod*fac[n-i]%mod;}ans%=mod,ans+=mod,ans%=mod;print(ans);return flush(),0;
}

总结

二项式反演还是挺有效的，也很好用，继续学习！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！