実は押すスイッチの集合が同じならば、それらを押す順番は最終的な \(B\) を変化させない。押されたスイッチに書かれた値を \(C_1, C_2, \cdots, C_K\) とする。このとき

• \(B_i\) とは \(C_i\) からいくつか選んで \(i\) を作る通り数の偶奇である。あるいは
• \(\mathbb F_2\) 上の多項式として\(B = \prod{(1 + x^{C_i})} \pmod {x^{N}}\)

と \(B\) は解釈することができる。どちらの解釈でもスイッチを押す順番は最終的な \(B\) に影響を与えないことが分かる。

これに加え、重要な事実が \(2\) つある。\(1\) つめは以下である。

• \(X\) が書かれたスイッチを \(2\) 個押すのと、\(2X\) が書かれたスイッチを \(1\) 個押すのは等価である

正当性は \((x + 1)^2 = x^2 + 1 \pmod 2\) を考えればよい。この変換を繰り返すことで、押すスイッチの値の集合をdistinctになるように変換可能である。

そして \(2\) つめの重要な事実は以下である。

• もし押すスイッチの値が distinct であることが分かっているならば、生成された \(B\) からスイッチの値の集合が復元可能である

これは以下を繰り返せばよい。

• \(B_i = 1\) なる最小の \(i\) から、押したスイッチの値の最小を求める
• 「もしこのスイッチを押さなかったらどうなるか」をFPS除算(戻すDP)により計算する

この \(2\) つの事実は「押すスイッチの値がdistinctになるように変換したあとの集合が、最終的な \(B\) を特徴づける」ということを示唆する。つまり、この問題は以下のように言い換えられる。

• \(A\) からいくつかの要素を選び、\(C\) とする
• \(C\) に同じ値 \(x\) が \(2\) つ以上存在するならば、これを \(2\) つ取り除き、代わりに \(2x \lt N\) ならば \(2x\) を追加する
• この操作を可能な限り繰り返したとき、最終的に出来る集合は何通りあるか？

この問題を考える。まず、\(A\) の値を奇数部分、つまり \(A_i\) を \(2\) で割れるだけ割ったあとに残る値、で分類してよいことが分かる。それぞれを独立に解けばよい。

分類後の問題は、 \(1, 2, 4, 8, ..., 2^{L-1}\) がいくつかあるので、これの総和として出来る値のうち \(2^{L}\) 以下のものは何種類か？ という問題になる。

最終的な値を固定したときに、それが達成可能か、という判定問題を考える。これは貪欲法で解くことが可能である。実際に下のbitから見ていき、\(1\) ならば対応するスイッチを \(1\) つ使う。そして、余ったスイッチを全て \(2\) 個組にして、\(2\) 倍の値のスイッチへ変換する。

この貪欲法を元に、最終的な値を下のbitから決めていく桁DPが実装可能である。伝搬するスイッチの個数が桁ごとに高々 \(2\) 種類しかないのが重要であり、\(O(L)\) 時間で動く。

\(L\) の合計は \(N\) であるため、合計で \(O(N + M)\) 時間でこの問題を解くことができる。