Permutation Game
题意翻译
$Alice$和$Bob$决定玩一个小游戏。游戏在一个有$n$个格子的直线上进行,格子标号为$1$~$n$,第$i$个格子里有一个数$ai(ai∈[1,n])$,并且,每个格子里的数各不相同。
现在在某个格子里有一个硬币。他们可以移动这个硬币,但是要将硬币从$i$号格子移动到$j$号格子里,必须满足下列条件:
1. $ai<aj$
2. $|i-j| mod \text{ } ai=0$
由$Alice$先手移动,谁不能移动硬币谁败。
现在问你当硬币的初始位置为$1$~$n$号格子的胜负情况(两人都采取最优策略)
题目描述
After a long day, Alice and Bob decided to play a little game. The game board consists of $ n $ cells in a straight line, numbered from $ 1 $ to $ n $ , where each cell contains a number $ a_i $ between $ 1 $ and $ n $ . Furthermore, no two cells contain the same number.
A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $ i $ to cell $ j $ only if the following two conditions are satisfied:
- the number in the new cell $ j $ must be strictly larger than the number in the old cell $ i $ (i.e. $ a_j > a_i $ ), and
- the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $ |i-j|\bmod a_i = 0 $ ).
Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.
输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of numbers.
The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ). Furthermore, there are no pair of indices $ i \neq j $ such that $ a_i = a_j $ .
输出格式
Print $ s $ — a string of $ n $ characters, where the $ i $ -th character represents the outcome of the game if the token is initially placed in the cell $ i $ . If Alice wins, then $ s_i $ has to be equal to "A"; otherwise, $ s_i $ has to be equal to "B".
输入输出样例
输入样例 #1
8
3 6 5 4 2 7 1 8
输出样例 #1
BAAAABAB
输入样例 #2
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
输出样例 #2
ABAAAABBBAABAAB
说明
In the first sample, if Bob puts the token on the number (not position):
- $ 1 $ : Alice can move to any number. She can win by picking $ 7 $ , from which Bob has no move.
- $ 2 $ : Alice can move to $ 3 $ and $ 5 $ . Upon moving to $ 5 $ , Bob can win by moving to $ 8 $ . If she chooses $ 3 $ instead, she wins, as Bob has only a move to $ 4 $ , from which Alice can move to $ 8 $ .
- $ 3 $ : Alice can only move to $ 4 $ , after which Bob wins by moving to $ 8 $ .
- $ 4 $ , $ 5 $ , or $ 6 $ : Alice wins by moving to $ 8 $ .
- $ 7 $ , $ 8 $ : Alice has no move, and hence she loses immediately.