前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態（必勝状態）に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。
これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、“移す"という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい（“移す"石の数が最小）ということになる。
$$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$
これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。
提出コードにコメントをつけておく。初期値は以下の通り。
rep(a, 2) {
ull b = a ^ (X & 1); // b は a から決まる
ull carry = a & b;
ull _sum = a ^ b;
if (_sum != (S & 1)) continue; // そもそも合計がS出なければスキップ
ull over = a > (A & 1);
chmax(dp[0][carry][over], a);
}
dp[i][j][k]からの遷移は以下の通り。配るDPなので i + 1 桁目について見ていく。
rep(i, M-1) rep(j, 2) rep(k, 2) rep(a, 2) {
if (dp[i][j][k] == -1) continue;
ull ni = i + 1;
ull b = a ^ ((X >> ni) & 1); // b は a から決まる
ull _sum = (a + b + j) & 1; // 合計を計算する場合には下の桁からの繰り上げを考慮する
ull _carry = ((a + b + j) & 2) > 0; // ni+1 桁目に対して、繰り上げがあるかどうか求める
if (_sum != ((S >> ni) & 1)) continue; // そもそも合計がS出なければスキップ
ull over;
if (a > ((A >> ni) & 1)) over = 1; // ni桁目まで見たとき、a が A を上回っているかどうか求める
if (a < ((A >> ni) & 1)) over = 0;
if (a == ((A >> ni) & 1)) over = k;
chmax(dp[i+1][_carry][over], dp[i][j][k] | (a << ni)); // dpを更新
}
自力では解けなかった。解説動画が分かりやすくて本当に助かっている。