G - Groups AtCoder Beginner Contest 217

atcoder.jp

解法

割り振り方において、Mで割った余りが異なる物同士は互いに影響を及ぼさないので、

割った余り毎にどう割り振るか組み合わせで考える。

また、K個ちょうどで考えると難しいので、K個のグループに分けるが0人のグループがあってもいいという風に考える

cou[m] := Mで割った余りがmになる人の数としたとき

dp0[k]:=K個のグループ分けであり0人のグループを許し、組に番号を付ける

dp[k]:=K個のグループ分けであり組に番号を付ける

とすると

dp0[k] = PI{m = 0 ~ M-1}(npr(k, cou[m])) ;

dp[k]  = dp0[k] - sigma(dp0[1~k-1] * com(k, 空いてるスペース))

となり

答えはdp[k] / k!