Chip Game

题意翻译

### 题目描述 $Alice$ 和 $Bob$ 在玩一个游戏. 游戏中有 $n$ 堆筹码, 其中第 $i$ 堆中有 $v_i$ 个筹码. 游戏开始前，$Alice$ 先从区间 $[1, m]$ 中选择一个正整数 $a$, 随后 $Bob$ 同样地选择一个正整数 $b$. 游戏开始. 在 $Alice$ 的回合中, 她可以选择任意至少包含 $a$ 个筹码的一堆, 然后从中取出 $a$ 个筹码. 同理, 在 $Bob$ 的回合中, 他也可以选择任意至少包含 $b$ 个筹码的一堆, 然后从中取出 $b$ 个筹码. 直到某回合不能继续操作的一方判负. 假设双方每次都会选择最优策略, 游戏结果将只由 $a$, $b$ 和 $先手次序$ 决定. 考虑一对选定的 $(a,b)$ , 则有四类可能的局面: * $Alice$ 必胜. * $Bob$ 必胜. * 先手必胜. * 后手必胜. 在所有合法的 $(a, b)$ 中 (即所有 满足 $1\leq a, b\leq m$ 的 $(a, b)$ 中), 请问每类局面各出现多少次. ### 输入格式 第一行有两个整数 $n$ 与 $m$. 其中 $n$ 表示筹码堆数, $m$ 表示游戏中抽取筹码的上限. 第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$, 分别表示每一堆的筹码数目. ### 输出格式 一行中输出四个整数$w_a , w_b , w_f , w_s$, 分别表示 $Alice$ 必胜, $Bob$ 必胜, 先手必胜, 后手必胜 的局面数 ### 说明/提示 样例\#1中共有四对可能的 $(a,b)$ * $a = b = 1$ : 每次可以从任意一堆取出筹码, 最终将进行 $9$ 回合, 先手将抽取最后一个筹码, 故先手必胜. * $a = b = 2$ : 游戏进行 $4$ 回合后将剩下包含 $1$ 个筹码的一堆. 此时先手无法继续操作, 后手必胜. * $a = 1$ 且 $b = 2$ : 此时 $Alice$ 有必胜策略，说明如下. * 假设 $Alice$ 先手: 首先 $Alice$ 从第二堆中取走 $1$ 个筹码. 此时每一堆中有 $4$ 个筹码. 随后每次都~~复读机~~复制 $Bob$ 的行为, 最后每堆都剩下 $1$ 个筹码, $Bob$ 无法继续操作, $Alice$ 胜利. * 假设 $Bob$ 先手: 如果 $Bob$ 从第二堆中取走筹码, 则 $Alice$ 从第一堆中取走筹码. 随后复制 $Bob$ 的行为即可获胜. 反之, 则 $Alice$ 也从第一堆中取走筹码. 此时第一堆中只剩下 $1$ 个筹码, $Bob$ 只能从第二堆中取走筹码. 此时第二堆剩余 $3$ 个筹码, 则此后不论 $Alice$ 如何操作均获胜. 综上， $Alice$ 必胜 * $a = 2$ 且 $b = 1$ : 同上, $Bob$ 必胜. 样例\#2中, 例如 $a = 7$ 且 $b = 6$ 等使得游戏开始后, 双方都无法取出筹码, 此时即后手必胜. 先手必胜的情况有: $(1, 1) , (1, 4) , (2, 3) , (3, 2) , (4, 1) , (5, 5)$ . ### 数据范围 $1 \leq n \leq 100, 1 \leq m \leq 10^5$ $1 \leq v_i \leq 10^{18}$

题目描述

Alice and Bob decided to play one ultimate game. They have $ n $ piles, the $ i $ -th pile initially contain $ v_i $ chips. Alice selects a positive integer $ a $ from interval $ [1, m] $ , and Bob selects a number $ b $ the same way. Then the game starts. In her turn, Alice can select any pile containing at least $ a $ chips, and remove exactly $ a $ chips from it. Similarly, in his turn, Bob can choose any pile with at least $ b $ chips, and remove exactly $ b $ chips from it. If a player cannot make a move, he or she loses. If both players play optimally, the outcome ultimately depends on the choice of $ a $ and $ b $ , and on the starting player. Consider a fixed pair $ (a,b) $ . There are four types of games: - Alice wins, regardless of who starts. - Bob wins, regardless of who starts. - If Alice starts, she wins. If Bob starts, he wins. We say that the first player wins. - If Alice starts, Bob wins. If Bob starts, Alice wins. We say that the second player wins. Among all choices of $ a $ and $ b $ (i.e. for each pair $ (a, b) $ such that $ 1\leq a, b\leq m $ ), determine how many games are won by Alice (regardless of who starts), how many are won by Bob (regardless of who starts), how many are won by the first player, and how many are won by the second player.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n \leq 100, 1 \leq m \leq 10^5 $ ) — the number of piles, and the upper bound on the number of chips allowed to be taken in one turn, respectively. The second line contains $ n $ integers $ v_1, v_2, \dots, v_n $ ( $ 1 \leq v_i \leq 10^{18} $ ) — the starting number of chips in each pile.

输出格式

Print a single line containing four integers $ w_a $ , $ w_b $ , $ w_f $ , $ w_s $ — the number of games won by Alice, Bob, the first player, the second player, respectively.

输入输出样例

输入样例 #1

2 2
4 5

输出样例 #1

1 1 1 1

输入样例 #2

2 20
4 5

输出样例 #2

82 82 6 230

说明

In the first sample, there are a total of four choices for the tuple $ (a,b) $ . - $ a = b = 1 $ : It does not matter from which pile the chips are removed — there are $ 9 $ turns to be made, and the first player also makes the last, and hence he wins. - $ a = b = 2 $ : The second player may win by always selecting the same pile as the first before there are $ 0 $ and $ 1 $ chips in the piles. Since it is impossible to remove $ 2 $ chips from any of them, the first player loses. - $ a = 1 $ and $ b = 2 $ : - Suppose Alice starts. She can win by removing a single chip from the pile with $ 5 $ chips and then copying Bob's decision. After the next four turns, the game ends with $ 1 $ chip in each pile and Bob unable to make a move. - Suppose Bob starts. If he removes two chips from second pile, Alice counters by removing a chip from the first pile. From then on, she can always copy Bob's decision and win. If Bob removes two chips from the first pile in his first turn, Alice can also remove one. As the first pile only has one chip left, Bob is forced to remove two chips from the second pile, leaving $ 3 $ . Regardless of what Alice does, she wins. Hence, Alice wins no matter who starts. - $ a = 2 $ and $ b = 1 $ : This is symmetric with the previous case — hence Bob always wins. In the second sample, a lot of games, e.g. $ a = 7 $ and $ b = 6 $ , end without anybody being able to remove single chip — which counts as a win for the second player. The games won for the first player are $ (1, 1) $ , $ (1, 4) $ , $ (2, 3) $ , $ (3, 2) $ , $ (4, 1) $ , and $ (5, 5) $ .