板刷計(jì)劃:ARC067

傳送門:https://atcoder.jp/contests/arc067/tasks/arc067_c

前言;又被組合數(shù)學(xué)dp教訓(xùn)了

C.水題

D.SB題

E.純組合數(shù)學(xué) + 動(dòng)態(tài)規(guī)劃(好題)

題目大意:

將n個(gè)人劃分成若干組。 每一組大小sz\in [A,B],每個(gè)大小出現(xiàn)的次數(shù)要么為0次，要么為[C,D]次.現(xiàn)在給你n,A,B,C,D,問你不同的方案數(shù)。兩個(gè)方案視作不同當(dāng)且僅當(dāng)存在兩個(gè)人，它只在某一個(gè)方案中存在于同一個(gè)組中.n <=1e3

例如: 7 1 3 1 2

只能分成: 2 + 2 + 3, 方案數(shù)為105種.

題目思路:

先考慮這個(gè)問題如何計(jì)數(shù):通過觀察樣例不難發(fā)現(xiàn)，就是組合數(shù)相乘。對于大小相同的組，要除一個(gè)全排列打消順序。

不難利用動(dòng)態(tài)規(guī)劃:dp(i,j)代表把i個(gè)人最多劃分成的組的大小為j的方案數(shù).形成前綴和的形式。我們枚舉從i個(gè)人中選k \in [C,D]個(gè)大小為j的組的方案數(shù)：

dp(i,j) = dp(i,j-1)+\sum_{k=C}^{D}\frac{i!}{(j!)^k*(i-kj)!} * \frac{1}{A_{k}^{k}}* dp(i - k j,j-1)

注意:式子右邊的常系數(shù)的推導(dǎo)如下:

C_{n}^{x}*C_{n - x}^{x}*...*C_{n - (k-1)x}^{x} =\frac{n!}{x!*(n-x)!} *\frac{(n-x)!}{x!*(n-2x)!} * ... * \frac{(n - (k-1)x)!}{x!*(n-kx)!} =v

\frac{n!}{(x!)^k *(n-kx)!} . 由于組之間無差別，所以還需要乘一個(gè)?\frac{1}{A_{k}^{k}}打消組間順序.

時(shí)間復(fù)雜度：

寫起來是三重循環(huán)的遞推,但不是n^3.大約分析如下:(估算復(fù)雜度上界)

\sum_{i=1}^n \sum_{j=A}^B\sum_{k=C}^{min(D,\frac{i}{j})}1 = \sum_{i=1}^n \sum_{j=A}^B \frac{i}{j}=\sum_{i=1}^n i*lni=n^2logn

注：第二步到第三步利用了調(diào)和級數(shù)定理.

復(fù)雜度上界為:\Theta (n^2logn)

AC代碼：https://atcoder.jp/contests/arc067/submissions/17136658

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容