Official
G - Groups Editorial by en_translator
The number of ways, \(DP[i][j]\), to divide \(i\) people (Person \(1\) to Person \(i\)) into exactly \(j\) group so that it satisfies the conditions, can be found with the following DP (Dynamic Programming):
\(DP[i][j]=DP[i-1][j-1]+\left(j-\left\lfloor\frac{i-1}{M}\right\rfloor\right)*DP[i-1][j]\)
in a total of \(O(N^2)\) time.
The intuition of the recurrence relations
Consider Person $i$. If the Person $i$ is the only member of the group he/she belongs, then the other $i-1$ people is divided into $j-1$ groups, so there are $DP[i-1][j-1]$ ways of such divisions. Otherwise, we assume that first $i-1$ people other than Person $i$ are divided into $j$ groups, and then Person $i$ will join one of them. Person $i$ can join such group in which no person's index has the same remainder divided by $M$ to that of $i$. There are $\left\lfloor\frac{i-1}{M}\right\rfloor$ such people, and they are all in different groups, so Person $i$ can join one of the remaining $j-\left\lfloor\frac{i-1}{M}\right\rfloor$. Therefore, there are $\left(j-\left\lfloor\frac{i-1}{M}\right\rfloor\right)*DP[i-1][j]$ such ways.A rather basic similar problem: AOJ『Balls and Boxes 9』
posted:
last update: