（日本語下手で失礼いたします。英語解説にも参照してください）

\(O\left( N(\log N+\log M) \right)\)の解法を紹介したいと思います。

元の問題に求められる「空でないかつ区別できない\(k\)個のグループに分ける」の場合の答えを\(f(k)\)とします。

また、「空でも構わないかつ区別できる\(k\)個のグループに分ける」の場合の答えを\(g(k)\)とします。その場合では、以下のような手順で分けられます。

\(r=0,1,\dots,M-1\)に対し、\(S_r=\{i|i\%M=r , 1\leq i \leq N\}\)を区別できる\(k\)個のグループに分ける。ただし、2つ以上の数を同じグループに入れられない

\(|S_r|=\lfloor N/M \rfloor\)のような\(S_r\)が\(M-N\%M\)個あり、\(|S_r|=\lfloor N/M \rfloor +1\)のような\(S_r\)が\(N\%M\)個あるので、\(g(k)\)は以下の式で（階乗を前計算すれば）一つの\(k\)に対して\(O(\log M)\)で計算できます。

\[ g(k)=\left( {}_kP_{\lfloor N/M \rfloor} \right)^{M-N\%M}\left( {}_kP_{\lfloor N/M \rfloor+1} \right)^{N\%M} \]

そして、\(f(k)\)で\(g(k)\)を表すこともできます。\(k'\leq k\)個の空でないかつ区別できないグループを\(k\)個の番号に対応させることを考えながら、以下の式で\(g(k)\)を表します。

\[ g(k)=\sum_{k'=0}^{k} {}_{k}P_{k'}f(k') \]

変形すると畳み込みの形になります。

\[ \frac{g(k)}{k!}=\sum_{k'=0}^{k} \frac{f(k')}{(k-k')!} \]

つまり、\([\frac{g(0)}{0!},\frac{g(1)}{1!},\frac{g(2)}{2!},\dots]\)は\([f(0),f(1),f(2),\dots]\)と\([\frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\dots]\)の畳み込みと等しいです。

\(g(k)\)を全部求めると\(O(N\log N)\)の逆畳み込みを一回行えば\(f(k)\)を全部求めます。あるいは、\(c(x)=\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\dots=e^x\)とし、\(c(x)c(-x)=e^xe^{-x}=1\)により、\([\frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\dots]\)の畳み込み逆元は\([\frac{1}{0!},-\frac{1}{1!},\frac{1}{2!},\dots]\)のことがわかり、普通の畳み込みでも\(f(k)\)を全部求めます。

よって総計算量は\(O\left( N(\log N+\log M) \right)\)です。

実装例(C++, 9ms) https://atcoder.jp/contests/abc217/submissions/25619059