CF1033C Permutation Game

一天劳累之后，Alice 和 Bob 决定玩一个小游戏。游戏棋盘由 $n$ 个格子组成，排成一行，编号从 $1$ 到 $n$，每个格子内包含一个 $1$ 到 $n$ 之间的数字 $a_i$。此外，任意两个格子内的数字都不相同。 一个棋子被放在某个格子上。他们轮流移动棋子，Alice 先手。当前玩家可以将棋子从第 $i$ 个格子移动到第 $j$ 个格子，只有当以下两个条件同时满足时才允许移动： - 新格子 $j$ 内的数字必须严格大于原格子 $i$ 内的数字（即 $a_j > a_i$）； - 本次移动的距离必须是原格子内数字的倍数（即 $|i-j| \bmod a_i = 0$）。 无法进行移动的一方判负。对于每一个可能的初始位置，若双方都采取最优策略，判断谁能获胜。 可以证明，游戏总是有限的，即总存在一方有必胜策略。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示格子的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。此外，任意 $i \neq j$ 都有 $a_i \neq a_j$。

输出一个长度为 $n$ 的字符串 $s$，其中第 $i$ 个字符表示若棋子初始放在第 $i$ 个格子时的游戏结果。如果 Alice 能获胜，则 $s_i$ 等于 "A"；否则，$s_i$ 等于 "B"。

在第一个样例中，若 Bob 将棋子放在数字（不是位置）： - $1$：Alice 可以移动到任意数字。她可以选择移动到 $7$，此时 Bob 无法再移动，Alice 获胜。 - $2$：Alice 可以移动到 $3$ 和 $5$。若她移动到 $5$，Bob 可以移动到 $8$ 并获胜。如果她选择移动到 $3$，则她获胜，因为 Bob 只能移动到 $4$，而 Alice 可以从 $4$ 移动到 $8$。 - $3$：Alice 只能移动到 $4$，之后 Bob 可以移动到 $8$ 并获胜。 - $4$、$5$ 或 $6$：Alice 可以直接移动到 $8$ 并获胜。 - $7$、$8$：Alice 无法移动，直接失败。 由 ChatGPT 4.1 翻译