已經(jīng)沒有什么好害怕的了

題目描述

已經(jīng)使\(\tt{Modoka}\)有簽訂契約，和自己一起戰(zhàn)斗的想法后，\(\tt{Mami}\)忽然感到自己不再是孤單一人了呢。

于是，之前的謹(jǐn)慎的戰(zhàn)斗作風(fēng)也消失了，在對\(\tt{Charlotte}\)的傀儡使用終曲——\(\tt{Tiro Finale}\)后，\(\tt{Mami}\)面臨著即將被\(\tt{Charlotte}\)的本體吃掉的局面。

這時，已經(jīng)多次面對過\(\tt{Charlotte}\)的\(\tt{Honiura}\)告訴了學(xué)\(OI\)的你這樣一個性質(zhì)：\(\tt{Charlotte}\)的結(jié)界中有兩種具有能量的元素，一種是“糖果”，另一種是“藥片”，各有\(n\)個。在\(\tt{Charlotte}\)發(fā)動進(jìn)攻前，“糖果”和“藥片”會兩兩配對，若恰好糖果比藥片能量大的組數(shù)比“藥片”比“糖果”能量大的組數(shù)多\(k\)組，則在這種局面下，\(\tt{Charlotte}\)的攻擊會丟失，從而\(\tt{Mami}\)仍有消滅\(\tt{Charlotte}\)的可能。

你必須根據(jù)\(\tt{Homura}\)告訴你的“糖果”和“藥片”的能量的信息迅速告訴\(\tt{Homura}\)這種情況的個數(shù).

輸入輸出格式

輸入格式：

第一行兩個整數(shù)\(n\),\(k\)，含義如題目所描述。

接下來一行\(n\)個整數(shù)，第\(i\)個數(shù)表示第\(i\)個糖果的能量。

接下來\(n\)個整數(shù)，第\(j\)個數(shù)表示第\(j\)個藥片的能量。

保證上面兩行不會有重復(fù)的數(shù)字

輸出格式：

一個答案，表示消滅\(\tt{Charlotte}\)的情況個數(shù)，要 \(\bmod (10^9 + 9)\)

說明

對于\(100\%\)的數(shù)據(jù)：\(l\le n\le 2000,0\le k\le n\)

---

因為元素互不相同，所以我們可以得到應(yīng)該有多少組糖果大于藥片，即為\(d=\frac{k+n}{2}\)

稱某個糖果\(i\)配對到比她少的藥品時為性質(zhì)\(i\)，則問題為 有多少種配對方案滿足恰好有滿足\(d\)個性質(zhì)。

令\(f_i\)為恰好滿足\(i\)的性質(zhì)的方案數(shù)，\(g_i\)為至少滿足\(i\)個性質(zhì)的方案數(shù)。

如果研究過容斥原理，而不是只浮于套路的表面，你會明白\(g_i\)實際上是自交的，畫個\(\text{veen}\)圖簡單解釋一下

每一個圓代表的方案集合為滿足某個性質(zhì)\(i\)的方案集合。

例如\(f_2\)為顏色不深不淺的黃色部分，而\(g_1\)為三個圓的面積之和（它的中間有交）

有

\[g_k=\sum_{i=k}^n\binom{i}{k}f_i\]

解釋一下，對于至少\(k\)個元素的集合，有\(i\)個元素的集合被重復(fù)計算了\(\binom{i}{k}\)次

\[f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i\]

這里就是在容斥了。

事實上上面的過程就是在進(jìn)行二項式反演,不過我沒有研究過它的一些證明，所以只能將就的感性理解了。

為什么要引入定義這么容易誤導(dǎo)的\(g_i\)（反正我最開始學(xué)的時候一直搞不懂“至少”）呢？

因為\(\tt{Ta}\)好算啊。

比如這個題，令\(dp_{i,j}\)代表前\(i\)個遞增的糖果已經(jīng)配對出了\(j\)對并且滿足\(j\)個性質(zhì)的方案數(shù)，有轉(zhuǎn)移

\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(p_i+1-j)\]

\(p_i\)代表糖果\(i\)大于多少個藥品，可以\(two-pointer\)也可以二分求

那么就有

\[g_i=dp_{n,i}\times fac_{n-i}\]

---

Code:

#include <cstdio> #include <algorithm> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define st(a,b) std::sort(a,b) #define lb(a,b,c) std::lower_bound(a,b,c)-(a); #define ll long long const int N=2010; const ll mod=1e9+9; ll quickpow(ll d,ll k) {ll f=1;while(k){if(k&1)f=f*d%mod;d=d*d%mod;k>>=1;}return f; } ll dp[N][N],g[N],inv[N],fac[N],ans; int m[N],c[N],p[N],n,k; int main() {scanf("%d%d",&n,&k);fac[0]=1;rep(i,1,n) scanf("%d",c+i),fac[i]=fac[i-1]*i%mod;rep(i,1,n) scanf("%d",m+i);if(k+n&1) return puts("0"),0;k=k+n>>1;inv[n]=quickpow(fac[n],mod-2);dep(i,n-1,0) inv[i]=inv[i+1]*(i+1)%mod;st(c+1,c+1+n),st(m+1,m+1+n);rep(i,1,n) p[i]=lb(m+1,m+1+n,c[i]);dp[0][0]=1;rep(i,1,n)rep(j,0,p[i])dp[i][j]=(dp[i-1][j]+(j?dp[i-1][j-1]*(p[i]+1-j):0))%mod;rep(i,k,n)g[i]=dp[n][i]*fac[n-i]%mod;rep(i,k,n)(ans+=(i-k&1?-1:1)*fac[i]%mod*inv[i-k]%mod*inv[k]%mod*g[i])%=mod;printf("%lld\n",(ans+mod)%mod);return 0; }

---

2018.10.23

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/9839081.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P4859 已经没有什么好害怕的了 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。