Alice是一名网络安全技术人员。这天她得到一串加密过的序列x1,x2,...,xnx_1,x_2,...,x_nx1​,x2​,...,xn​。并且她知道，从原序列y加密成新序列x的加密方式是xi=yi⊕ax_i = y_i\oplus axi​=yi​⊕a，且原序列所有数的和为S。 她想请你帮忙破解这个加密序列，你需要找到一个非负的最小的a使得 xi=yi⊕ax_i = y_i\oplus axi​=yi​⊕a 且 ∑i=1nyi=S\sum_{i=1}^{n} y_i = S∑i=1n​yi​=S。⊕\oplus⊕代表二进制按位异或运算。

这道题可以使用异或性质和数学方法来解决。

首先，我们知道异或运算的性质：a ⊕ a = 0，a ⊕ 0 = a，a ⊕ b = b ⊕ a，a ⊕ b ⊕ c = a ⊕ (b ⊕ c)。

因此，如果我们将原序列和新序列都异或一遍，得到的结果就是：

S ⊕ (a ⊕ S) ⊕ (a * x1) ⊕ (a * x2) ⊕ ... ⊕ (a * xn)

= S ⊕ (a ⊕ a) ⊕ (a * x1) ⊕ (a * x2) ⊕ ... ⊕ (a * xn)

= S ⊕ (a * x1) ⊕ (a * x2) ⊕ ... ⊕ (a * xn)

= (y1 ⊕ a) ⊕ (y2 ⊕ a) ⊕ ... ⊕ (yn ⊕ a)

= y1 ⊕ y2 ⊕ ... ⊕ yn ⊕ (a ⊕ a ⊕ ... ⊕ a)

= y1 ⊕ y2 ⊕ ... ⊕ yn

由于我们已经知道了原序列所有数的和为S，因此我们可以计算出y1 ⊕ y2 ⊕ ... ⊕ yn的值，设为T。

那么，我们只需要找到一个最小的非负整数a，使得T ⊕ (a * x1) ⊕ (a * x2) ⊕ ... ⊕ (a * xn) = 0。

这个问题可以转化成求一个线性同余方程T ≡ a * (x1 ⊕ x2 ⊕ ... ⊕ xn) (mod 2)，然后解出a的值。

因为异或运算满足结合律和交换律，所以x1 ⊕ x2 ⊕ ... ⊕ xn的值可以预处理出来，设为B。

如果B等于0，那么a可以是任意非负整数。

如果B不等于0，那么方程T ≡ a * B (mod 2)只有两种情况：有解和无解。

如果有解，那么方程的解为a = T / B。

如果无解，那么说明原序列和新序列的异或和不相等，无法破解。

综上所述，我们可以按照上述方法求解出a的值。