(出題: hotman)

同じ数字が書かれたボールが二個であることから、区別のつかない箱の集合の大きさは、ボールが一個以上入っている場合は高々 \(2\) 個です。

よって、以下のように DP することでこの問題を \(O\left(NK^2\right)\) で解くことができます。

\(dp_{a,b,c} = \) \(1 \ldots a\) までのボールを入れた後、どの箱とも区別のつく箱が \(b\) 個、区別のつかない箱のペアが \(c\) 個であるような場合の数