CF #779 (Div. 2) - F. Juju and Binary String 解法
$ 1の総数を$ Kとして、$ R = \frac{MK}{N}が整数であることが必要である。
これが成り立つとき、つねに$ k \leq 2の答えが存在する。
数列が円環であるとして考える。$ s_i, \dots, s_{i + M - 1}における$ 1の個数を$ c_iで表すことにすると、
$ \sum c_i = MKであるので$ c_iの最小値は$ R以下、最大値は$ R以上である。
そして、$ c_i, c_{i + 1}の差分を考えると$ |c_i - c_{i + 1}| \leq 1とわかる。
よって、中間値の定理の離散バージョンを適用すると、$ c_i = Rとなる$ iが存在する。
累積和 + $ iを全探索で答えが求められる。