CF1634B Fortune Telling

题目描述

哈哈，来试试解决这个问题吧，SelectorUnlimited！

—— antontrygubO_o

你的朋友 Alice 和 Bob 正在练习占卜。

占卜的过程如下。有一个众所周知的数组 $a$，长度为 $n$，下标从 $1$ 到 $n$，每个元素都是非负整数。被占卜者从某个非负整数 $d$ 开始，对于每个 $i = 1, 2, \ldots, n$（按 $i$ 递增顺序），可以选择以下两种操作之一：

• 用 $d + a_i$ 替换当前的数字 $d$；
• 用 $d \oplus a_i$ 替换当前的数字 $d$（这里 $\oplus$ 表示按位异或运算）。

注意，对于不同的 $i$ 和不同的被占卜者，可以选择不同的操作。

有一次，Alice 决定以 $d = x$ 开始，而 Bob 以 $d = x + 3$ 开始。他们各自完成了占卜，最后得到了某个特定的数字。注意，两位朋友选择的操作是独立的，也就是说，对于同一个 $i$，他们可以选择不同的操作。

你得知最后得到的数字 $y$ 是 Alice 或 Bob 中某一位的结果，但你不知道具体是谁。给定 Alice 和 Bob 的起始数字以及 $y$，请你判断最后得到 $y$ 的可能是谁（Alice 或 Bob）。保证在所有评测点上，只有一位朋友有可能得到该数字。

Hack

本题不允许进行 Hack。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来的 $2 \cdot t$ 行描述每个测试用例。

每个测试用例的第一行包含三个整数 $n$、$x$、$y$（$1 \le n \le 10^5$，$0 \le x \le 10^9$，$0 \le y \le 10^{15}$），分别表示数组 $a$ 的长度、Alice 的初始数字（Bob 的初始数字为 $x+3$），以及最终得到的数字 $y$。

每个测试用例的第二行包含 $n$ 个整数，表示数组 $a$（$0 \le a_i \le 10^9$）。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，表示最终可能得到数字 $y$ 的朋友的名字："Alice" 或 "Bob"。

4
1 7 9
2
2 0 2
1 3
4 0 1
1 2 3 4
2 1000000000 3000000000
1000000000 1000000000

Alice
Alice
Bob
Alice

说明/提示

在第一个测试用例中，Alice 可以通过如下操作得到 $9$：$7 + 2 = 9$。

在第二个测试用例中，Alice 可以通过如下操作得到 $2$：$(0 + 1) \oplus 3 = 2$。

在第三个测试用例中，Bob 的起始数字为 $x+3=0+3=3$，可以通过如下操作得到 $1$：$(((3 + 1) + 2) \oplus 3) \oplus 4 = 1$。

由 ChatGPT 4.1 翻译