#P4. [CSP-S 2024] We are the champion

[CSP-S 2024] We are the champion

题目描述

小 S 想要举办一场擂台游戏,如果共有 2k2^k 名选手参加,那么游戏分为 kk 轮进行:

  • 第一轮编号为 1,21, 2 的选手进行一次对局,编号为 3,43, 4 的选手进行一次对局,以此类推,编号为 2k1,2k2^k - 1, 2^k 的选手进行一次对局。
  • 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
  • 以此类推,第 k1k - 1 轮在只保留第 k2k - 2 轮的 44 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。
  • kk 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选手都有一个能力值 a1,a2,,a2ka_1, a_2, \dots , a_{2^k},能力值为 [0,2311][0,2^{31}-1] 之内的整数。对于每场比赛,会先抽签决定一个数 0/10/1,我们将第 RR 轮的第 GG 场比赛抽到的数记为 dR,Gd_{R,G}。抽到 00 则表示表示编号小的选手为擂主,抽到 11 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 aRa\geq R。也就是说,游戏的胜负只取决于擂主的能力值当前比赛是第几轮的大小关系,与另一位的能力值无关

现在,小 S 先后陆续收到了 nn 位选手的报名信息,他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 1,2,,n1, 2, \dots, n。小 S 关心的是,补充尽量少的选手使总人数为 22 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可能成为总冠军的选手的编号之和是多少。

形式化地,设 kk 是最小的非负整数使得 2kn2^k\geq n,那么应当补充 (2kn)(2^k-n) 名选手,且补充的选手的能力值可以任取 [0,2311][0,2^{31}-1] 之内的整数。如果补充的选手有可能取胜,也应当计入答案中

当然小 S 觉得这个问题还是太简单了,所以他给了你 mm 个询问 c1,c2,,cmc_1,c_2,\dots,c_m。小 S 希望你帮忙对于每个 cic_i 求出,在只收到前 cic_i 位选手的报名信息时,这个问题的答案是多少。

输入格式

本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改 a1,a2,,ana_1, a_2, \dots , a_n 得到,其他内容均保持不变,请参考以下格式。其中 \oplus 代表异或运算符,amodba \bmod b 代表 aa 除以 bb 的余数。

输入的第一行包含两个正整数 n,mn, m,表示报名的选手数量和询问的数量。

输入的第二行包含 nn 个非负整数 a1,a2,,ana'_1,a'_2,\dots,a'_n,这列数将用来计算真正的能力值。

输入的第三行包含 mm 个正整数 c1,c2,,cmc_1, c_2, \dots , c_m,表示询问。

KK 是使得 2Kn2^K \geq n 的最小的非负整数,接下来的 KK 行当中,第 RR 行包含 2KR2^{K-R} 个数(无空格),其中第 GG 个数表示第 RR 轮的第 GG 场比赛抽签得到的 dR,G=0/1d_{R,G}=0/1

注意,由于询问只是将人数凑齐到 2kci2^k\geq c_i,这里的 kKk\leq K,因此你未必会用到全部的输入值。

接下来一行包含一个正整数 TT,表示有 TT 组测试数据。

接下来共 TT 行,每行描述一组数据,包含 44 个非负整数 X0,X1,X2,X3X_0,X_1,X_2,X_3,该组数据的能力值 ai=aiXimod4a_i=a'_i \oplus X_{i\bmod 4},其中 1in1\leq i\leq n

输出格式

共输出 TT 行,对于每组数据,设 AiA_i 为第 ii1im1 \leq i \leq m)组询问的答案,你只需要输出一行包含一个整数,表示 $(1\times A_1) \oplus (2\times A_2) \oplus \dots \oplus (m\times A_m)$ 的结果。

样例

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1
5
19
7
1

提示

【样例 1 解释】

共有 T=4T = 4 组数据,这里只解释第一组。55 名选手的真实能力值为 [1,0,0,2,1][1, 0, 0, 2, 1]55 组询问分别是对长度为 5,4,1,2,35, 4, 1, 2, 3 的前缀进行的。

  1. 对于长度为 11 的前缀,由于只有 11 号一个人,因此答案为 11
  2. 对于长度为 22 的前缀,由于 22 个人已经是 22 的幂次,因此不需要进行扩充。根据抽签 d1,1=1d_{1,1} = 1 可知 22 号为擂主,由于 a2<1a_2 < 1,因此 11 号获胜,答案为 11
  3. 对于长度为 33 的前缀,首先 11 号、22 号比赛是 11 号获胜(因为 d1,1=1d_{1,1} = 1,故 22 号为擂主,a2<1a_2 < 1),然后虽然 44 号能力值还不知道,但 33 号、44 号比赛一定是 44 号获胜(因为 d1,2=0d_{1,2} = 0,故 33 号为擂主,a3<1a_3 < 1),而决赛 11 号、44 号谁获胜都有可能(因为 d2,1=1d_{2,1} = 1,故 44 号为擂主,如果 a4<2a_4 < 211 号获胜,a42a_4 \geq 244 号获胜)。综上所述,答案为 1+4=51 + 4 = 5
  4. 对于长度为 44 的前缀,我们根据上一条的分析得知,由于 a42a_4 \geq 2 ,所以决赛获胜的是 44 号。
  5. 对于长度为 55 的前缀,可以证明,可能获胜的选手包括 44 号、77 号、88 号,答案为 1919

因此,该组测试数据的答案为 $(1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5$。

【样例 2】

见选手目录下的 arena/arena2.in 与 arena/arena2.ans。

这组样例满足特殊性质 A。

【样例 3】

见选手目录下的 arena/arena3.in 与 arena/arena3.ans。

这组样例满足特殊性质 B。

【样例 4】

见选手目录下的 arena/arena4.in 与 arena/arena4.ans。

【样例 5】

见选手目录下的 arena/arena5.in 与 arena/arena5.ans。

【数据范围】

对于所有测试数据,保证:2n,m1052 \leq n, m \leq 10^50ai,Xj<2310 \leq a_i, X_j < 2^{31}1cin1 \leq c_i \leq n1T2561 \leq T \leq 256

测试点 T=T= n,mn,m\leq 特殊性质 A 特殊性质 B
131\sim 3 11 88
4,54,5 500500
686\sim 8
9,109,10 50005000
11,1211,12 10510^5
131513\sim 15
16,1716,17 44
18,1918,19 1616
20,2120,21 6464
22,2322,23 128128
24,2524,25 256256

特殊性质 A:保证询问的 cic_i 均为 22 的幂次。

特殊性质 B:保证所有的 dR,G=0d_{R,G} = 0