No.3569 Xor to Zero
Problem Statement
Consider the following game, played using a sequence of positive integers $C=(C_1,C_2,\dots,C_k)$.
Initially, $k$ piles of stones are arranged in a row from left to right, and the $i$-th pile from the left contains $C_i$ stones. $2$ players alternately perform the following operation.
- Choose the leftmost pile among those with $1$ or more stones remaining, and remove $1$ or more stones from the chosen pile.
- If, after the operation, the bitwise XOR of the numbers of stones over all piles is $0$, the player who performed the operation wins and the game ends.
Here, let $f(C)$ be the total number of operations performed by the $2$ players until the game ends, when the $2$ players play optimally.
Optimal play means the following: if a player can win, they choose, among the winning moves, one that minimizes the total number of operations; if a player cannot win, they choose a move that maximizes the total number of operations.
You are given a sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ of length $N$.
There are $\displaystyle \frac{N(N+1)}{2}$ possible non-empty contiguous subarrays $A_{l,\,r}=(A_l,A_{l+1},\dots,A_r)$ of $A$. Find the sum of $f(A_{l,\,r})$ over all of them.
Constraints
- All input values are integers.
- $1\le N\le 10^5$
- $1\le A_i\le 10^6\quad(1\le i\le N)$
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the answer as an integer on $1$ line.
Sample
Sample 1
Input
3 1 2 3
Output
12
For example, when the game is played with $A_{1,\,3}=(1,\,2,\,3)$, the following sequence of operations is possible.
- First player: takes $1$ stone $\rightarrow(0,\,2,\,3)$
- Second player: takes $1$ stone $\rightarrow(0,\,1,\,3)$
- First player: takes $1$ stone $\rightarrow(0,\,0,\,3)$
- Second player: takes $3$ stones $\rightarrow(0,\,0,\,0)$
The second player's last operation makes the bitwise XOR of the numbers of stones over all piles equal to $0$, so the second player wins. It can be shown that these operations are optimal, so $f(A_{1,\,3})=4$.
Sample 2
Input
10 3 1 4 1 5 9 2 6 5 3
Output
170
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu