C. Permutation Game
brute force; dp; games
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"".
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.