人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder Regular Contest 067:E - Grouping

問題

atcoder.jp

解法

dp(i, j) := i 人をグループ人数 j 以上のグループに分けるときの通り数

と DP を定義する.このとき,

dp(i, j) = dp(i - j * k, j + 1) * c / k! (C <= k <= D, c = C(i, j) * C(i - j, j) * ... * C(i - j * (k - 1), j))

と漸化式が立つので計算すればよい.一見 O(N^3) に見えるが,k は高々 i / j までに抑えられるので,

N / 1 + N / 2 + ... + N / N ≒ NlogN

より O(N^2 * logN).

解答

atcoder.jp

実装において,mod の世界での割り算を単純に / d などとしていたため,WA を連発してしまっていた.正しくは * mod_inverse(d) とするべきだった(代わりに割る数の逆元をかける).

f:id:babcs2035:20181229183816p:plain