ZerOne 2

解説

$dp[i][j][k]:=$ 先頭 $i$ 項目まで決め、$M$ で総和を割ったあまりは $j$ で、最後の項が $2$ であるかどうかが $k$
とすれば、$O(NM)$ で解くことができます。

一方、$2$ の個数を決め打ってみます。このとき、総和が $M$ の倍数になるような $1$ の個数の決め方の総数は $O(\frac{N}{M})$ 程度です。
また、これらを決めれば $0$ の個数も分かります。よって、あとは $2$ が隣り合わないような並べ方の総数が分かればよく、これは先に $0$ と $1$ を並べて間または両端に $2$ を並べる方法を求めれば良いです。
これで $O(\frac{N^2}{M})$ でも解くことができます。

$\min(NM, \frac{N^2}{M})$ は $N\sqrt{N}$ 程度なので、$M$ に応じて使い分けることでこの問題が $O(N\sqrt{N})$ で解けました。

余談

これ を出すときに一緒に出そうと思ってたんですが没になっていました

お願い

間違いあればコメントで指摘を頂けると嬉しいです。