Official

G - Groups Editorial by kyopro_friends

人1,…,i1,\ldots,i の ii 人を条件を満たしつつちょうど jj 個のグループに分ける方法の数を DP[i][j]DP[i][j] として

DP[i][j]=DP[i−1][j−1]+(j−⌊i−1M⌋)∗DP[i−1][j]DP[i][j]=DP[i-1][j-1]+\left(j-\left\lfloor\frac{i-1}{M}\right\rfloor\right)*DP[i-1][j]

というDPにより O(N2)O(N^2) で求めることができます。

漸化式の気持ち 人 ii に注目します。
人 ii が1人グループをなす場合、残りの i−1i-1 人で j−1j-1 個のグループを作るので、そのような方法の数は DP[i−1][j−1]DP[i-1][j-1] になります。
そうでない場合、まず人 ii 以外の i−1i-1 人で jj 個のグループを作り、出来たグループのいずれかに人 ii が合流すると考えます。人 ii が合流できるグループは、MM で割った余りが ii と等しい番号の人を含まないようなものに限ります。そのような人は ⌊i−1M⌋\left\lfloor\frac{i-1}{M}\right\rfloor 人おり、この人たちは相異なるグループに属しているので、人 ii が合流できるグループは j−⌊i−1M⌋j-\left\lfloor\frac{i-1}{M}\right\rfloor 個です。したがって、そのような方法の数は (j−⌊i−1M⌋)∗DP[i−1][j]\left(j-\left\lfloor\frac{i-1}{M}\right\rfloor\right)*DP[i-1][j] となります。


より基本的な類題：AOJ『Balls and Boxes 9』

posted:
last update:

2025-04-09 (Wed)
02:16:12 +00:00