傳送門: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è)人劃分成若干組憔辫。 每一組大小,每個(gè)大小出現(xiàn)的次數(shù)要么為0次颈娜，要么為
次.現(xiàn)在給你n,A,B,C,D,問(wèn)你不同的方案數(shù)。兩個(gè)方案視作不同當(dāng)且僅當(dāng)存在兩個(gè)人麸俘，它只在某一個(gè)方案中存在于同一個(gè)組中.
例如: 7 1 3 1 2
只能分成: 2 + 2 + 3, 方案數(shù)為105種.
題目思路:
先考慮這個(gè)問(wèn)題如何計(jì)數(shù):通過(guò)觀察樣例不難發(fā)現(xiàn)，就是組合數(shù)相乘递沪。對(duì)于大小相同的組丸冕，要除一個(gè)全排列打消順序。
不難利用動(dòng)態(tài)規(guī)劃:形成前綴和的形式除盏。我們枚舉從i個(gè)人中選
個(gè)大小為j的組的方案數(shù)：
注意:式子右邊的常系數(shù)的推導(dǎo)如下:
. 由于組之間無(wú)差別叉橱，所以還需要乘一個(gè)?
打消組間順序.
時(shí)間復(fù)雜度：
寫起來(lái)是三重循環(huán)的遞推,但不是n^3.大約分析如下:(估算復(fù)雜度上界)
注：第二步到第三步利用了調(diào)和級(jí)數(shù)定理.
復(fù)雜度上界為:
AC代碼：https://atcoder.jp/contests/arc067/submissions/17136658
