問題一覧 > 通常問題

No.2672 Subset Xor Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 138
作問者 : NokonoKotlinNokonoKotlin / テスター : XelmephXelmeph nu50218nu50218 nullnull ngtkanangtkana 👑 eoeoeoeo
8 ProblemId : 10670 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-15 21:21:48

問題文

長さ $N$ の非負整数列 $A = (A_1 , A_2 , \dots , A_N)$ が与えられます。

数列 $A$ を以下の条件を満たす $2$ つの部分列 $B = (B_1, B_2, \dots, B_M)$ と $C = (C_1, C_2, \dots, C_{N-M})$ に分割したいです。

  • $1 \leq M \leq N-1$
  • $B_1 \oplus B_2 \oplus \dots \oplus B_M = 0$
  • $C_1 \oplus C_2 \oplus \dots \oplus C_{N-M} = 0$

ただし $\oplus$ はビットごとの排他的論理和（Bitwise XOR）です。

上記の分割が可能なら Yes を、不可能なら No を出力してください。

数列 $A$ を $2$ つの部分列 $B$ と $C$ に分割するとは
以下の操作のことをいいます。
  1. $B, C$ を空の数列とする。
  2. 各 $i = 1, 2, \dots, N$ について、この順に $A_i$ を $B$ の末尾または $C$ の末尾に加える。

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

上記の分割が可能なら Yes を、不可能なら No を出力し、改行してください。

制約

  • 入力はすべて整数
  • $2 \leq N \leq 5 \times 10^5$
  • $0 \leq A_i \leq 5000$

サンプル

サンプル1
入力
6
1 12 4 3 2 8
出力
Yes

たとえば $B = (12 , 4 , 8), C = (1, 3, 2)$ と分割すると、上記の条件を満たします。

サンプル2
入力
4
1 3 8 10
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。