CF2276G Elimination of Players

在某个游戏中，有 $n$ 个玩家，编号从 $1$ 到 $n$。每个玩家有一个实力值——它是 $1$ 到 $n$ 之间的整数，并且所有玩家的实力值互不相同。实力值的分布由一个排列 $(s_1, s_2, \ldots, s_n)$ 给出，其中 $s_j$ 是第 $j$ 个玩家的实力。 一开始，所有玩家都会参加游戏。游戏一共进行 $n-1$ 轮。第 $i$ 轮中，编号为 $a_i$ 的玩家获得保护。被保护的玩家也可能已经被淘汰。 每一轮恰好有一位玩家被淘汰。淘汰规则如下： - 如果剩下的玩家中，实力值最小的玩家未被保护，则淘汰该玩家； - 否则，淘汰剩下玩家中实力值第二小的玩家。 被淘汰的玩家不再参与后续的游戏。经过最后一轮后，恰好剩下一个玩家。 已知序列 $a_1, a_2, \ldots, a_{n-1}$，但未知具体的实力分布。对于每个玩家 $j$ 和每轮 $i$，请你计算有多少种排列 $(s_1, s_2, \ldots, s_n)$ 会让玩家 $j$ 在第 $i$ 轮被淘汰。

第一行包含一个整数 $t$（$1 \le t \le 2500$），表示测试用例数。 每个测试用例包括两行： - 第一行包含一个整数 $n$（$2 \le n \le 5000$），表示玩家数。 - 第二行包含 $n-1$ 个整数 $a_1, a_2, \ldots, a_{n-1}$（$1 \le a_i \le n$），表示每轮中被保护的玩家编号。$a_i$ 可能重复。 输入的额外约束： - 所有测试用例中 $n$ 的总和不超过 $5000$。

对于每组测试数据，按如下方式输出答案： 设 $ans(i,j)$ 表示对于某种 $(s_1, s_2, \ldots, s_n)$，第 $i$ 个玩家在第 $j$ 轮被淘汰的排列数，对 $998\,244\,353$ 取模。请输出一个整数，等于 $$ \oplus_{i=1}^{n} \oplus_{j=1}^{n-1} (ans(i,j)\cdot i\cdot j) $$ 其中 $\oplus$ 表示按位异或（XOR）。只有 $ans(i,j)$ 对 $998\,244\,353$ 取模，$ans(i,j)\cdot i\cdot j$ 的乘积和最终答案不取模。

在第一个测试用例中，可能的实力分布有 $(1,2)$ 和 $(2,1)$。唯一一轮中，第 $2$ 个玩家被保护，因此两种情况下都是第 $1$ 个玩家被淘汰。所以 $ans(1,1)=2$，$ans(2,1)=0$，答案为 $$ (2\cdot 1\cdot 1)\oplus(0\cdot 2\cdot 1)=2。 $$ 在第二个测试用例中，总共有 $6$ 种实力分布。$ans(i,j)$ 的取值如下表：行对应玩家，列对应回合。 $$ \begin{array}{c|cc} & j=1 & j=2 \\ \hline i=1 & 0 & 5 \\ i=2 & 3 & 0 \\ i=3 & 3 & 1 \end{array} $$ 第 $1$ 个玩家在第一轮被保护，第 $2$ 个玩家在第二轮被保护，对应的 $ans$ 值为零。第二轮，第 $1$ 个玩家在 $5$ 种分布下会被淘汰，第 $3$ 个玩家只在 $(3,1,2)$ 这一种分布下被淘汰。将表中数值分别乘以玩家编号和轮数后，最终答案为 $$ 0\oplus 10\oplus 6\oplus 0\oplus 9\oplus 6=3。 $$ 在第三个测试用例中，总共有 $24$ 种实力分布。第 $1$ 个玩家在每一轮都被保护，永远不会被淘汰，其余三名玩家是对称的，所以每个人每一轮都有 $24/3=8$ 种情况会被淘汰。$ans(i,j)$ 的表如下： $$ \begin{array}{c|ccc} & j=1 & j=2 & j=3 \\ \hline i=1 & 0 & 0 & 0 \\ i=2 & 8 & 8 & 8 \\ i=3 & 8 & 8 & 8 \\ i=4 & 8 & 8 & 8 \end{array} $$ 第 $1$ 个玩家对应的乘积全为零。对剩下玩家的乘积进行异或，得到答案： $$ 16\oplus 32\oplus 48\oplus 24\oplus 48\oplus 72\oplus 32\oplus 64\oplus 96=96。 $$ 由 ChatGPT 5 翻译