CF2276G.Elimination of Players

提高+/省选-

通过率:0%

时间限制:4.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

In a certain game, there are nn players numbered from 11 to nn. Each player has a strength — an integer from 11 to nn. All players have distinct strengths. The distribution of strengths is given by a permutation (s1,s2,…,sn)(s_1, s_2, \ldots, s_n), where sjs_j is the strength of player jj.

Initially, all players take part in the game. The game consists of n−1n-1 rounds. In the ii-th round, the player aia_i is protected. It is possible that the protected player was already eliminated.

In each round, exactly one player is eliminated. This player is chosen as follows:

  • if the player with the minimum strength among the remaining players is not protected, that player is eliminated;
  • otherwise, the player with the second minimum strength among the remaining players is eliminated.

An eliminated player no longer takes part in the game. After the last round, exactly one player remains.

You are given the sequence a1,a2,…,an−1a_1, a_2, \ldots, a_{n-1}, but the distribution of strengths is unknown. For each player jj and each round ii, find the number of permutations (s1,s2,…,sn)(s_1, s_2, \ldots, s_n) for which the player jj is eliminated in the ii-th round.

在某个游戏中,有 nn 名玩家,编号从 11 到 nn。每名玩家有一个强度值——一个介于 11 到 nn 之间的整数。所有玩家的强度互不相同。强度的分布由一个排列 (s1,s2,…,sn)(s_1, s_2, \ldots, s_n) 给出,其中 sjs_j 表示玩家 jj 的强度。

初始时,所有玩家均参与游戏。游戏共进行 n−1n-1 轮。在第 ii 轮中,玩家 aia_i 被保护。被保护的玩家可能已被淘汰。

每轮恰好淘汰一名玩家。被淘汰的玩家按如下规则选定:

  • 若剩余玩家中强度最小者未被保护,则该玩家被淘汰;
  • 否则,淘汰剩余玩家中强度第二小者。

被淘汰的玩家不再参与后续游戏。经过最后一轮后,恰好剩一名玩家。

已知序列 a1,a2,…,an−1a_1, a_2, \ldots, a_{n-1},但强度分布未知。对每个玩家 jj 和每轮 ii,求使得玩家 jj 在第 ii 轮被淘汰的排列 (s1,s2,…,sn)(s_1, s_2, \ldots, s_n) 的个数。

输入格式

The first line contains one integer tt (1≤t≤25001 \le t \le 2500) — the number of test cases.

Each test case consists of two lines:

  • the first line contains one integer nn (2≤n≤50002 \le n \le 5000) — the number of players;
  • the second line contains n−1n-1 integers a1,a2,…,an−1a_1, a_2, \ldots, a_{n-1} (1≤ai≤n1 \le a_i \le n) — the numbers of the protected players in the corresponding rounds. The values aia_i may repeat.

Additional constraints on the input:

  • the sum of nn over all test cases does not exceed 50005000.

第一行包含一个整数 tt(1≤t≤25001 \le t \le 2500)—— 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 nn(2≤n≤50002 \le n \le 5000)—— 玩家数量;
  • 第二行包含 n−1n-1 个整数 a1,a2,…,an−1a_1, a_2, \ldots, a_{n-1}(1≤ai≤n1 \le a_i \le n)—— 对应各轮中受保护玩家的编号。值 aia_i 可能重复。

输入的额外约束:

  • 所有测试用例的 nn 值之和不超过 50005000。

输出格式

For each test case, print the answer in the following way:

Let ans(i,j)ans(i,j) denote the number of permutations (s1,s2,…,sn)(s_1, s_2, \ldots, s_n) for which player ii is eliminated in round jj, taken modulo 998 244 353998\,244\,353. Print one integer equal to ⊕i=1n⊕j=1n−1(ans(i,j)⋅i⋅j)\oplus_{i=1}^{n} \oplus_{j=1}^{n-1} (ans(i,j)\cdot i\cdot j), where ⊕\oplus denotes the bitwise exclusive OR (XOR) operation. Only the values ans(i,j)ans(i,j) are taken modulo 998 244 353998\,244\,353; the products ans(i,j)⋅i⋅jans(i,j)\cdot i\cdot j and the final answer are not.

对每个测试用例,按如下方式输出答案:

令 ans(i,j)ans(i,j) 表示满足“玩家 ii 在第 jj 轮被淘汰”的排列 (s1,s2,…,sn)(s_1, s_2, \ldots, s_n) 的个数,对 998 244 353998\,244\,353 取模。输出一个整数,其值为 ⊕i=1n⊕j=1n−1(ans(i,j)⋅i⋅j)\oplus_{i=1}^{n} \oplus_{j=1}^{n-1} (ans(i,j)\cdot i\cdot j),其中 ⊕\oplus 表示按位异或(XOR)运算。仅 ans(i,j)ans(i,j) 对 998 244 353998\,244\,353 取模;乘积 ans(i,j)⋅i⋅jans(i,j)\cdot i\cdot j 及最终答案均不取模。

输入输出样例

  • 输入#1

    7
    2
    2
    3
    1 2
    4
    1 1 1
    4
    1 4 1
    7
    2 2 2 7 7 7
    6
    3 1 3 6 3
    5
    5 1 4 2

    输出#1

    2
    3
    96
    188
    2024
    4610
    69

说明/提示

In the first test case, there are two possible distributions of strengths: (1,2)(1,2) and (2,1)(2,1). In the only round, player 22 is protected, so in both cases player 11 is eliminated. Thus, ans(1,1)=2ans(1,1)=2, ans(2,1)=0ans(2,1)=0, and the answer is $ (2\cdot 1\cdot 1)\oplus(0\cdot 2\cdot 1)=2. $

In the second test case, there are 66 possible distributions of strengths. The values of ans(i,j)ans(i,j) are shown in the table: rows correspond to players, columns — to rounds. $ \begin{array}{c|cc} & j=1 & j=2 \ \hline i=1 & 0 & 5 \ i=2 & 3 & 0 \ i=3 & 3 & 1 \end{array} $ Player 11 is protected in the first round, and player 22 — in the second, so the corresponding values are zero. In the second round, player 11 is eliminated for five strength distributions, and player 33 — only for the distribution (3,1,2)(3,1,2). After multiplying the table values by the player and round numbers, we get the answer $ 0\oplus 10\oplus 6\oplus 0\oplus 9\oplus 6=3. $

In the third test case, there are 2424 possible distributions of strengths. Player 11 is protected in all rounds and is never eliminated. The other three players are symmetric, so each of them is eliminated in each round for 24/3=824/3=8 strength distributions. The table of values ans(i,j)ans(i,j) is $ \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} $ The products for player 11 are zero. The XOR of the products for the remaining players gives the answer $ 16\oplus 32\oplus 48\oplus 24\oplus 48\oplus 72\oplus 32\oplus 64\oplus 96=96. $

在第一个测试用例中,力量值的分配方案共有两种:(1,2)(1,2) 和 (2,1)(2,1)。在唯一的一轮中,玩家 22 受到保护,因此在这两种情况下,玩家 11 均被淘汰。于是有 ans(1,1)=2ans(1,1)=2,ans(2,1)=0ans(2,1)=0,答案为 (2⋅1⋅1)⊕(0⋅2⋅1)=2(2\cdot 1\cdot 1)\oplus(0\cdot 2\cdot 1)=2。

在第二个测试用例中,力量值的分配方案共有 66 种。ans(i,j)ans(i,j) 的取值如以下表格所示:行对应玩家编号,列对应轮次。
j=1j=2i=105i=230i=331 \begin{array}{c|cc} & j=1 & j=2 \\ \hline i=1 & 0 & 5 \\ i=2 & 3 & 0 \\ i=3 & 3 & 1 \end{array}
第一轮中玩家 11 受到保护,第二轮中玩家 22 受到保护,因此对应位置的值为零。在第二轮中,玩家 11 在五种力量分配下被淘汰,而玩家 33 仅在力量分配 (3,1,2)(3,1,2) 下被淘汰。将表格中各值分别乘以对应的玩家编号与轮次编号后,得到答案 $ 0\oplus 10\oplus 6\oplus 0\oplus 9\oplus 6=3 $。

在第三个测试用例中,力量值的分配方案共有 2424 种。玩家 11 在所有轮次中均受保护,因此永远不会被淘汰。其余三名玩家具有对称性,故每名玩家在每一轮中均恰好在 24/3=824/3=8 种力量分配下被淘汰。ans(i,j)ans(i,j) 的取值表如下:
j=1j=2j=3i=1000i=2888i=3888i=4888 \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}
玩家 11 对应的所有乘积均为零。剩余玩家对应乘积的异或结果即为答案:$ 16\oplus 32\oplus 48\oplus 24\oplus 48\oplus 72\oplus 32\oplus 64\oplus 96=96 $。

输入解题思路,AI测评打分。不知道怎么写?

首页