問題一覧 > 通常問題

No.3569 Xor to Zero

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 4
作問者 : 👑 to-omer / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 9892 / 自分の提出
問題文最終更新日: 2026-03-21 00:07:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 501 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。