ABC156:E-簡單組合數(shù)學(xué)

傳送門:https://atcoder.jp/contests/abc156/tasks/abc156_e

題目大意：給你n個房間，每個房間里一個人。一次移動可以使得一個人移動到除本身外的任意一個房間里去。問k次移動之后，房間有多少種組合狀態(tài)。

例如： n = 3 , k = 2.

狀態(tài)有:(0,0,3),(0,3,0),(3,0,0),(0,1,2),(0,2,1),(1,2,0),(2,1,0),(1,1,1),(1,0,2),(2,0,1).

題目思路：

當(dāng) k\geq n時,任何局面可以達(dá)成，就是求不定方程非負(fù)整數(shù)解的個數(shù).我們可以用一一映射+插空法。答案為：C(2*n-1,n-1)

當(dāng) k< n時.等價于：x_1+...+x_n=n \ \ 且 \ \max\{x_i\} \leq \min\{n,1+k\}

當(dāng)時我推到這里就卡住了。想用dp做，但是只能想出O(n^2)的.

因為我這里漏掉了一個很重要的條件: 未知數(shù)的個數(shù) = 所求的數(shù).

那么就意味著，當(dāng)存在著一個數(shù) >= k 時，那么必將至少有 k - 1 個空格產(chǎn)生.

所以上述條件可以轉(zhuǎn)換為:局面中存在有[0,k]個空房間。

那么我們可以用總的減去不合法的，當(dāng)然也可以直接算。

空房間的組合情況為：C(n,i)

剩下來的房間最少都有1個人，那么可以直接插空法:C(n-1,n-i-1)

總答案為：\sum_{i=0}^{k}C(n,i)*C(n-1,n-i-1)

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

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