前言

繼續學習容斥的技巧！

題意簡介

題面鏈接

題目大意

給出兩個數組$a,b$
求有多少種對應方式使得有恰好$k$對匹配$(i,j)$滿足$a_i>b_j$

數據范圍

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

題解

部分分

這道題的暴力是指數級的，對于這樣的數據范圍顯得非常沒有意義

正解

發現暴力的瓶頸在于枚舉匹配的集合，那么說明我們不能直接枚舉集合
考慮減少限制，使得計算變得簡單，然后再把不滿足的都扔掉，那么就能做出這道題，也就是容斥
我們先將兩個數組分別排序，這樣的話容易發現對于$a$中的一個元素$a_i$，滿足$a_i>b_j$的$b_j$是$b$的一個前綴
定義$g[i]$為最大的下標$j$滿足$b_j<a_i$
定義$f[i][j]$表示$a$數組的前$i$個數，其中確定有$j$對匹配滿足$a>b$（確定那么多，但不代表只有那么多），在這樣的情況下這$j$對的選擇方案數（這$j$對以外的數的匹配不同算同一種方案）
然后很容易貼出轉移式子$$f[i][j+1]=f[i?1][j+1]+f[i?1][j]?(g[i]?j)$$
第一項代表當前這個數不匹配，第二項表示當前這個數匹配
設$F[i]=f[n][i]?(n?i)!$，那么$F[i]$就表示滿足$a>b$的匹配對數大于等于$j$的對應方式數（注意，這個定義和上面的不同，乘一個階乘后就所有數都固定了）
定義$Ans[i]$表示滿足$a>b$的匹配對數等于$j$的對應方式數
容易發現$Ans[k]$即我們所要的答案
我們發現這樣一個顯然的式子$$F[k]=\sum _{i=k}^n\left(\genfrac{}{}{0ex}{}{i}{k}\right)Ans[i]$$
注：$\left(\genfrac{}{}{0ex}{}{i}{j}\right)=C(i,j)$即組合數
二項式反演即可得$$Ans[k]=\sum _{i=k}^n(?1{)}^{i?k}(\genfrac{}{}{0ex}{}{i}{k})F[i]$$
那么什么是二項式反演呢？請看下一節
我們先把這題講完，假設你推出了這個，那么就可以直接算答案了
前面$dp$的復雜度是$\Theta (n^2)$的，后面的答案計算由于只要算一個所以是$\Theta (n)$的
綜上，總復雜度$\Theta (n^2)$

二項式反演

二項式反演的經典形式為$$f_n=\sum _{i=0}^n(?1{)}^i(\genfrac{}{}{0ex}{}{n}{i})g_i?g_n=\sum _{i=0}^n(?1{)}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)f_i$$
這篇博客用到的式子是另一個經典模型
$$f_i=\sum _{j=0}^i\left(\genfrac{}{}{0ex}{}{n?j}{n?i}\right)g_j?g_i=\sum _{j=0}^i(?1{)}^{i?j}(\genfrac{}{}{0ex}{}{n?j}{n?i})f_j$$
應用的時候其實是進行了數組翻轉和特殊值代換產生的
要問證明？請看我的另一篇總結博客

代碼

東西講完了，就可以安心寫出前面的那一題了，貼上ac代碼

#include<cstdio> #include<cctype> #include<algorithm> 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; }

總結

二項式反演還是挺有效的，也很好用，繼續學習！

總結

以上是生活随笔為你收集整理的二项式反演[bzoj3622]已经没有什么好害怕的了的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。