Still Light

元ネタはこの問題です https://codeforces.com/contest/1630/problem/D （まだ見れるかな？）

$x_i \lt x_j$ としたとき、操作 $i$ と操作 $j$ から、連続 $x_j-x_i$ 個の電球をつけたり消したりする操作が作られます。 したがって、最終的に $\gcd(x_1,x_2,...,x_M)$ が得られ、この操作のみを使うことにして良いということが容易にわかります。

$g=(x_1,x_2,...,x_M)$ として、パリティ $p_i$ を次のように定めます。

• $j\equiv i\pmod{g}$ である電球 $j$ としてあり得る電球のうち、明かりがついているものが奇数個なら、$p_i=1$
• $j\equiv i\pmod{g}$ である電球 $j$ としてあり得る電球のうち、明かりがついているものが偶数個なら、$p_i=0$

連続 $g$ 個の電球の状態を反転させる操作を行うと、全てのパリティ $p_i$ $(0\le i\lt g)$ の値が反転します。これは、連続 $g$ 個の整数の中には $g$ で割ったあまりが $i$ $(0\le i\lt g)$ になるような数が必ず $1$ つだけ現れることからわかります。

実は、パリティが全て $0$ か $1$ に一致するような、明かりがついている電球の集合の個数が答えになります。

必要性はわかったので十分性のきもちを確かめます。

パリティが一致するような任意の電球の集合を考えます。XOR演算の性質から、操作の終わった状態 $A$ からさらに操作を繰り返して始状態に戻すことができれば、行った操作を逆順に行うことで始状態からその状態 $A$ がえられることがわかります。 パリティが一致するような任意の電球の集合において、操作を繰り返して始状態に戻せることを確認しましょう。

明かりがついている電球のうち最も番号の小さいものを $l$ 、最も番号の大きいものを $r$ とします。操作を電球 $r-g+1, r-g+2, ..., r$ に対して行います。行えないなら、$l, l+1, ..., l+g-1$ に対して行います。 この操作のあとに明かりがついている電球のうち最も番号の小さいものを $l'$ 、最も番号の大きいものを $r'$ とすると、$r'-l'\lt r-l$ となるため操作を繰り返していけば始状態に戻ることが言えます。

これらのことから、答えは二項定理より $2^{(floor(N/g)-1)(g-r)+(ceil(N/g)-1)r+1}$ （ただし、$N$ を $g$ で割ったあまりを $r$ とします）