As prerequisite knowledge, it’s good to know that this is a game called Nim. Nim has a winning strategy: take XOR of the number of stones in all piles $A_i$, and if the result is anything other than 0, the person whose turn it is can always win with optimal moves. When your turn comes in a winning state with XOR != 0, by cleverly removing a certain number of stones from a certain pile, you can transition to a state with XOR = 0. Conversely, from a state with XOR = 0, no matter what choice you make, you inevitably transition to a state with XOR != 0 (winning state). Since the total number of stones decreases as turns progress, the game will always end. This is apparently called a Grundy number.
Based on this, let’s proceed with consideration. It says “by moving 0 or more stones less than $A_1$ from the first pile to the second pile…”, so we only need to consider the first two piles. From now on, let $A=A_1$, $B=A_2$, $X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$. Also, rephrase the “move” operation as changing $A$ to $a$ and $B$ to $b$. Then, while satisfying the following conditions, we should maximize $a$ as much as possible (minimum number of stones to “move”).
$$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$
This can be solved by digit DP. Let $dp_{i,j,k}$ be the maximum value of $a$ when looking up to the $i$-th digit from the bottom. However, if there’s a carry to the digit above, $j=1$, and if $a$ exceeds $A$ when looking up to the $i$-th digit, $k=1$. Looking at about 50 digits is sufficient.
I’ll add comments to the submitted code. Initial values are as follows:
rep(a, 2) {
ull b = a ^ (X & 1); // b is determined from a
ull carry = a & b;
ull _sum = a ^ b;
if (_sum != (S & 1)) continue; // Skip if sum isn't S in the first place
ull over = a > (A & 1);
chmax(dp[0][carry][over], a);
}
Transition from dp[i][j][k] is as follows. Since it’s distribution DP, we look at the i + 1-th digit.
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 is determined from a
ull _sum = (a + b + j) & 1; // When calculating sum, consider carry from lower digit
ull _carry = ((a + b + j) & 2) > 0; // Determine if there's carry to ni+1 digit
if (_sum != ((S >> ni) & 1)) continue; // Skip if sum isn't S in the first place
ull over;
if (a > ((A >> ni) & 1)) over = 1; // When looking up to ni digit, determine if a exceeds 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)); // Update dp
}
I couldn’t solve it on my own. The explanation video is very clear and truly helpful.