Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly $\frac{n}{2}$ cards, so each card belongs to exactly one player. Then, they take turns. Alex goes first, then Boris, then Alex again, and so on.
On a player’s turn, he must play exactly one of his cards. Then, if the opponent doesn’t have any cards stronger than the card played, the opponent loses, and the game ends. Otherwise, the opponent has to play a stronger card (exactly one card as well). These two cards are removed from the game, and the turn ends. If there are no cards left, the game ends in a draw; otherwise it’s the opponent’s turn.
Consider all possible ways to distribute the cards between two players, so that each of them receives exactly half of the cards. You have to calculate three numbers:
- the number of ways to distribute the cards so that Alex wins;
- the number of ways to distribute the cards so that Boris wins;
- the number of ways to distribute the cards so that the game ends in a draw.
/*
和局看似只有1
必须如此出牌:
Alex Boris
n - 1 n
n - 2 n - 3
n - 5 n - 4
games is beautiful
我们设置i-th表示牌n - i + 1
A代表先手,B代表后手
和局的模式为BAABBAAB···,长度为n
第一个不同的人获胜
我们可以使用dp(xyt)形式的动态编程,
x代表A的数目,y代表B的数目,t代表状态0,1,2
t = 2代表和局,t = 0代表先手胜,t = 1代表后手胜。
转移方程:dp[0][0][2] = 1
可以用i + j代表长度
dp[i + 1][j][t] += dp[i][j][t]
dp[i][j + 1][t] += dp[i][j][t]
此外,
(i + j) % 4 == 0 || 3时,
先手可以dp[i + 1][j][0] += dp[i][j][2];
相同的逻辑,(i + j) % 4 == 1 || 2时,
后手dp[i][j + 1][1] += dp[i][j][2].
请注意,只有在和棋的基础上改变才会影响战局。
*/