← 返回题目列表

AtCoder · awc0057_a

A. 加密继电器

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥正在设计一种加密系统,通过 N 服务器。

在这个系统中, N 服务器连成一线,编号 1, 2, \ldots, N 从左到右。每个服务器 i (1 \leq i \leq N) 有一个加密密钥 A_i (非负整数)分配给它。

在数据传输之前,加密密钥 每个服务器实际使用的 B_i 由以下规则确定。的价值 B_i 仅根据原始加密密钥确定 A_1, A_2, \ldots, A_N,并且对所有服务器同时完成。

  • 服务器 j (2 \leq j \leq N-1)如果满足以下条件,则被称为“夹心异常服务器”: A_{j-1} = A_{j+1} 和 A_{j-1} \neq A_j。换句话说,两个相邻服务器的加密密钥是相等的,而它自己的加密密钥与它们的不同。
  • 对于服务器 j 被确定为“夹心异常服务器”, B_j = 0.
  • 对于所有其他服务器 j (服务器 1,服务器 N,以及不满足上述条件的服务器), B_j = A_j.

接下来,非负整数数据 X 按照以下规则从左到右传输。让 D_0 = X,以及每个服务器 i (按顺序 i = 1, 2, \ldots, N) 接收数据 D_{i-1} 并计算 D_i = D_{i-1} \oplus B_i (\oplus 表示按位异或)。数据 服务器收到 D_0 服务器收到 1 是数据 X 由高桥发送,以及 D_N 由服务器计算 N 是最终输出数据。

给定数据 Takahashi 发送到服务器的 X 高桥发送到服务器 1 和各个服务器的加密密钥,求出最终输出数据 D_N.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq X \leq 10^9
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数

输入

N X
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 代表服务器数量,非负整数 X 代表 Takahashi 最初发送的数据,以空格分隔。
  • 第二行包含 N 非负整数 A_i 代表每个服务器的加密密钥 i (1 \leq i \leq N),用空格分隔。

输出

在一行上打印最终输出数据。


示例输入 1

5 10
1 2 1 3 3

示例输出 1

10

示例输入 2

3 5
7 7 7

示例输出 2

2

示例输入 3

8 123
8 1 8 3 3 5 7 5

示例输出 3

123

示例输入 4

20 999999999
0 1000000000 0 5 5 7 8 7 3 3 3 9 1 9 4 6 4 2 2 2

示例输出 4

999999998

示例输入 5

1 0
0

示例输出 5

0