\(X\) の下から \(0, \ldots, k\) 番目のビットを \(T\) のそれと一致させたいとします。

• その過程で \(1\) を足すことによって \(k - 1\) 番目のビットから \(k\) 番目のビットへの繰り上がりが生じない場合、\(k\) 番目のビットは XOR の影響のみを受けるため、\(0, \ldots, k - 1\) 番目のビットを一致させた上で、使った XOR によって \(k\) 番目のビットも一致しなければならない。
• \(k - 1\) 番目のビットから \(k\) 番目のビットへの繰り上がりが生じる場合、繰り上がり後に \(0, \ldots, k - 1\) 番目のビットが \(0\) となる。その後、\(0\) から \(T\) に遷移すればよい。

このように、大きい部分問題は、初期値と目標値の異なる小さい部分問題に帰着し、使った XOR の上位ビットへの影響を記録する必要があることが分かります。上位ビットでの繰り上がりを記録せずに済むように、一つの部分問題では、現在のビット番号を越える繰り上がりは一度だけとします。

形式的には、部分問題 \((k, s, f, M)\) を次のように定義します。

• \(k\) は一致させたい下位ビットの個数である。
• \(s\) は部分問題における \(X\) の初期値を定義する。
  • \(s = 0\) なら、はじめ \(X = S\) である。
  • \(s = 1\) なら、はじめ \(X = 0\) である。
• \(f\) は \(X\) の目標値と繰り上がり制約を定義する。
  • \(f = 0\) なら、目標値は \(T\) であり、ビット \(k - 1 \to k\) で繰り上がりが生じてはならない。
  • \(f = 1\) なら、目標値は \(0\) であり、ビット \(k - 1 \to k\) で繰り上がりがちょうど一度、最後の操作（加算である必要がある）において生じなければならない。
• \(M\) は長さ \(n\) のビットマスクである。\(M_i = 0\)（\(M_i = 1\)）なら、操作 \(X \to X \oplus Y_i\) を行う回数は偶数（奇数）でなければならない。

この部分問題の解決に必要な最小コストを \(cost(k, s, f, M)\) と定義します。\(B = 40\) をビットの個数として、答えは \(\min_M cost(B, 0, 0, M)\) です。

\(k\) の昇順に \(cost(k, \ldots)\) を全て計算していきます。\(k = 0\) のときは、何も一致させる必要がありませんが、\(cost(0, s, 0, M) = \sum_{i \in M} C_i, cost(0, s, 1, M) = A + \sum_{i \in M} C_i\) です（\(1\) の加算は、ビット \(k - 1 \to k\) での繰り上がりとして扱えます）。

\((k + 1, s, f, M)\) の解を、ビット \(k - 1 \to k\) での繰り上がりに基づいて分類します。すると、可能な解は以下のようになります。

• 任意の \(s, M\) について、もし \(M\) で指定された XOR を適用すると \(X\) のビット \(k\) が所望の値になる場合、\((k, s, 0, M)\) の解が \((k + 1, s, 0, M)\) の解となる。
• そうでない場合、ビット \(k - 1 \to k\) で繰り上がりが一度は生じなければならない。従って、\((k, s, 1, M_0), (k, 1, 1, M_1), \ldots, (k, 1, f, M_t)\) という列が解となる。ここで、\(M_i\) の値を用いれば \(X\) のビット \(k\) の経過を追えることに注意し、ビット \(k \to k + 1\) での繰り上がりが生じるべきときにのみ生じるようにする。

よって、\(cost(k, s, f, M)\) を求めることは、最適な「部分問題列」を構築することに帰着します。これは最短経路問題といえます。ここで、グラフの辺は上記の部分問題 \((k - 1, s, f, M)\) であり、頂点 \((x, M)\) は以下のように中間状態を表します。

• \(x\) は次の部分問題の直前における \(X\) のビット \(k\) の値であり、
• \(M\) は現在までに累積されたビットマスクである。

最短経路は、例えばダイクストラ法で求めることができます。実は、\((k, 1, 1, M_i)\) という種類の遷移を使うのは常に一度以下で十分であることが証明できますが、この問題を解くのに必要ではなく、解法の高速化にも役立ちません。

この解法の計算量は \(O(B 2^{2N})\) です。

なお、解が存在するなら、\(2^{40}\) 回以下の加算と \(2\) 回の XOR のみからなる解が必ず存在するため、答えは \(2 \cdot 10^{17}\) 以下となります。