ARC 067 E - Grouping

• 問題
• AC

$x$人を$A$人以上かつ$y$人以下からなるグループにわける場合の数を$f(x, y)$とすると、求める数は$f(N, B)$である。

漸化式を考える。$y$人のグループを1つも作らない分け方は$f(x, y-1)$に等しい。また、$y$人のグループをちょうど$k$個作る分け方は

$f(x-ky, y-1)\binom{x}{y}\binom{x-y}{y}...\binom {x-(k-1)y}{y} \frac{1}{k!} = \\ f(x-ky, y-1)\frac{x!}{(x-ky)! (y!)^k} \frac{1}{k!}$

である。（同人数のグループの区別はないので、$k$個のグループを作ったあと$k!$で割っている。）したがって、漸化式は

$f(x, y) = f(x, y-1) + \sum_{k \in \{C, C+1, ...,D\}}f(x-ky, y-1) \frac{x!}{(x-ky)! (y!)^k} \frac{1}{k!}$

と書ける。ただし$f(0, y) = 1$であり、また、$y < A$なら$f(x, y) = 0$である。

計算量について。$ky \le x \le N$という条件により、与えられた$y \in \{1, 2, ..., B\}$に対して有効な$k$は高々$N/y$種類しかないから、遷移の総数は$\sum_y N/y = {\mathcal O}(N \log N)$。したがって、全体の計算量は${\mathcal O}(N^2 \log N)$。