AT_abc255_g [ABC255G] Constrained Nim

题目描述

高桥君和青木君用由若干石子组成的 $N$ 个山堆进行石子取走游戏。

开始时，对于 $i = 1, 2, \ldots, N$，第 $i$ 个山堆有 $A_i$ 个石子。游戏由高桥君先手，二人轮流重复以下操作：

选择一个至少剩有 $1$ 个石子的山堆，从该山堆中取走至少 $1$ 个石子。

但本游戏有 $M$ 种禁手，不能进行属于禁手的操作。
对于 $i = 1, 2, \ldots, M$，第 $i$ 种禁手是“从恰好有 $X_i$ 个石子的山堆中恰好取走 $Y_i$ 个石子”。

无法进行操作的一方判负，未判负的一方获胜。假设双方都采取最优策略，请判断最终哪位玩家会获胜。

输入格式

输入以以下格式从标准输入给出。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

如果高桥君获胜，输出 Takahashi；如果青木君获胜，输出 Aoki。

输入输出样例 #1

输入 #1

3 4
1 2 4
2 1
3 3
3 1
1 1

输出 #1

Takahashi

输入输出样例 #2

输入 #2

1 5
5
5 1
5 2
5 3
5 4
5 5

输出 #2

Aoki

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{18}$
• $1 \leq Y_i \leq X_i \leq 10^{18}$
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
• 所有输入均为整数

样例解释 1

对于 $i = 1, 2, 3$，设第 $i$ 个山堆的石子数为 $A'_i$，用数列 $A' = (A'_1, A'_2, A'_3)$ 表示各山堆当前的石子数。游戏开始前，$A' = (1, 2, 4)$。游戏进行的一种可能如下：

• 首先，高桥君从第 $3$ 个山堆取走 $1$ 个石子，结果 $A' = (1, 2, 3)$。
• 接着，青木君从第 $2$ 个山堆取走 $2$ 个石子，结果 $A' = (1, 0, 3)$。
• 然后，高桥君从第 $3$ 个山堆取走 $2$ 个石子，结果 $A' = (1, 0, 1)$。

此时，第 $1$ 个和第 $3$ 个山堆还各剩 $1$ 个石子，但由于“从恰好有 $1$ 个石子的山堆中恰好取走 $1$ 个石子”属于第 $4$ 种禁手，青木君无法进行操作。因此，高桥君获胜。

由 ChatGPT 4.1 翻译