Permutation Game

1000ms

262144K

Description:

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.

Input:

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$$$.

Output:

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".

Sample Input:

8
3 6 5 4 2 7 1 8

Sample Output:

BAAAABAB

Sample Input:

15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

Sample Output:

ABAAAABBBAABAAB

Note:

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.

Informação

Provedor Codeforces

Código CF1033C