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.

题意翻译

$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$号格子的胜负情况(两人都采取最优策略)