P14586 [LNCPC 2025] 前后缀石子博弈

Z 形管道猫邀请我们的老朋友 Alice 和 Bob 来玩他们俩最喜欢的取石子博弈游戏啦……这次是基于前后缀的取石子规则和初始局面生成规则。

在一局游戏中，局面由一行 $m$ 堆石子构成，从前往后是从第 $1$ 堆到第 $m$ 堆。Alice 和 Bob 两人轮流取石子。Alice 先取。 在一轮取石子中，本轮操作的玩家首先**选择**两个**非负整数** $get_{pre},get_{suf}$，然后从前 $get_{pre}$ 个有石子的堆中每堆各取走 $1$ 颗石子，并且从后 $get_{suf}$ 个有石子的堆中每堆各取走 $1$ 颗石子，但是在同一轮同一堆中最多只能取走 $1$ 颗石子。 最先在其的一个操作轮中取走 $0$ 颗石子的玩家输掉本局游戏，另一个玩家胜利。 Alice 和 Bob 将玩 $n$ 局游戏。记 $a_{i,j}$ 表示在第 $i$ 局游戏的初始局面中第 $j$ 堆的石子数。**给定**两个**非负整数** $ put_{pre},put_{suf}(put_{pre}+put_{suf}\le m)$ 和第 $1$ 局游戏的初始局面 $a_{1,1},\cdots,a_{1,m}$。 第 $i(i\in[2,n])$ 局游戏的初始局面的生成规则是：首先基于第 $i-1$ 局游戏的初始局面，然后对前 $put_{pre}$ 堆的石子数取该部分的后缀和，并且对后 $put_{suf}$ 堆的石子数取该部分的前缀和，其余部分保持不变。\ 更正式地， $$a_{i,j}=\begin{cases} \sum\limits_{k=j}^{put_{pre}}a_{i-1,k} & j\in[1,put_{pre}]\\ a_{i-1,j} & j\in[put_{pre}+1,m-put_{suf}]\\ \sum\limits_{k=m-put_{suf}+1}^{j}a_{i-1,k} & j\in[m-put_{suf}+1,m] \end{cases}$$ Alice 和 Bob 都将采用最优策略。请您判断在这 $n$ 局游戏中每一局的胜者。

每个测试点包含多组测试数据。第一行给定一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。 对于每组测试数据：\ 第一行给定四个整数 $n,m,put_{pre},put_{suf}(1\le n\le10^6,1\le m\le10^6,put_{pre}\ge 0,put_{suf}\ge 0,put_{pre}+put_{suf}\le m)$，分别表示总游戏局数，初始局面的总石子堆数和生成初始局面的两个非负整数。\ 第二行给定 $m$ 个整数 $a_{1,j}(1\le a_{1,j}\le10^9)$，其中第 $j$ 个整数 $a_{1,j}$ 表示在第 $1$ 局游戏的初始局面中第 $j$ 堆的石子数。 保证在每个测试点中所有测试数据的 $n$ 的总和不超过 $10^6$，$m$ 的总和不超过 $10^6$。

对于每组测试数据，输出共 $n$ 行，每行一个字符串。对于其中第 $i$ 行，若第 $i$ 局游戏将是 Alice 胜利，则输出 `Alice`；否则（第 $i$ 局游戏将是 Bob 胜利），输出 `Bob`。

对于样例的第一组测试数据： 第 $1$ 局游戏的初始局面为 $1,3,1,2,1,2,2$。 下面是 Alice 和 Bob 可能的博弈过程： 1. Alice 选择 $get_{pre}=4,get_{suf}=0$，取走 $4$ 颗石子，局面变为 $0,2,0,1,1,2,2$，即（仅保留有石子的堆） $2,1,1,2,2$。 2. Bob 选择 $get_{pre}=1,get_{suf}=2$，取走 $3$ 颗石子，局面变为 $1,1,1,1,1$。 3. Alice 选择 $get_{pre}=2,get_{suf}=3$，取走 $5$ 颗石子，此时局面中所有堆都没有石子。 4. Bob 选择 $get_{pre}=0,get_{suf}=0$，取走 $0$ 颗石子。Bob 输掉本局游戏，Alice 胜利。 第 $2$ 局游戏的初始局面为 $5,4,1,2,1,2,4$。 第 $3$ 局游戏的初始局面为 $10,5,1,2,1,2,6$。 对于样例的第二组测试数据，第 $2$ 局游戏的初始局面为 $7,10,18,21,26,36$。 本题的输入输出量较大，请注意所使用的输入输出方式。 最后 Alice 和 Bob 玩吐了，希望他们俩以后别再玩取石子博弈游戏了……