擂台游戏(arena)
【题目描述】
小 S 想要举办一场擂台游戏,如果共有 2k 名选手参加,那么游戏分为 k 轮进行:
第一轮编号为 1, 2 的选手进行一次对局,编号为 3, 4 的选手进行一次对局,以此
类推,编号为 2k − 1, 2k 的选手进行一次对局。
第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
以此类推,第 k − 1 轮在只保留第 k − 2 轮的 4 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。
第 k 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选 手都有一个能力值 a1 , a2 , · · · , a2k ,能力值为 [0, 231 − 1] 之内的整数。对于每场比赛,会 先抽签决定一个数 0/1,我们将第 R 轮的第 G 场比赛抽到的数记为 dR,G。抽到 0 则表 示表示编号小的选手为擂主,抽到 1 则表示编号大的选手为擂主。擂主获胜当且仅当他 的能力值 a ≥ R。也就是说,游戏的胜负只取决于擂. 主. 的. 能. 力. 值. 与当. 前. 比. 赛. 是. 第. 几. 轮. 的 大小关系,与. 另. 一. 位. 的. 能. 力. 值. 无. 关. 。
现在,小 S 先后陆续收到了 n 位选手的报名信息,他们分别告知了小 S 自己的能 力值。小 S 会按照报名的先后顺序对选手进行编号为 1, 2, · · · , n。小 S 关心的是,补充 尽. 量. 少. 的选手使总人数为 2 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可 能成为总冠军的选手的编. 号. 之. 和. 为多少。
形式化地,设 k 是最小的非负整数使得 2k ≥ n,那么应当补充 (2k − n) 名选手,且 补充的选手的能力值可以任取[0,231−1]之内的整数。如.果.补.充.的.选.手.有.可.能.获.胜.,也. 应. 当. 计. 入. 答. 案. 中. 。
当然小 S 觉得这个问题还是太简单了,所以他给了你 m 个询问 c1, c2, · · · , cm。小 S 希望你帮忙对于每个 ci 求出,在只收到前 ci 位选手的报名信息时,这个问题的答案 是多少。
【输入格式】
从文件 arena.in 中读入数据。
本. 题. 的. 测. 试. 点. 包. 含. 有. 多. 组. 测. 试. 数. 据.,但不同测试数据只是通过修改a1,a2,··· ,an 得 到,其他内容均保持不变,请参考以下格式。其中 ⊕ 代表异或运算符,a mod b 代表 a 除以 b 的余数。
输入的第一行包含两个正整数 n, m,表示报名的选手数量和询问的数量。
输入的第二行包含 n 个非负整数 a′1, a′2, · · · , a′n,这列数将用来计算真正的能力值。
输入的第三行包含 m 个正整数 c1, c2, · · · , cm,表示询问。
设K是使得2K ≥n的最小的非负整数,接下来的K行当中,第R行包含2K−R个数(无空格),其中第 G 个数表示第 R 轮的第 G 场比赛抽签得到的 dR,G = 0/1。
注意,由于询问只是将人数凑齐到 2k ≥ ci,这里的 k ≤ K,因此你未必会用到全部 的输入值。
接下来一行包含一个正整数 T,表示有 T 组测试数据。
接下来共 T 行,每行描述一组数据,包含 4 个非负整数 X0, X1, X2, X3,该组数据 的能力值ai =a′i ⊕Ximod4,其中1≤i≤n。
【输出格式】
输出到文件 arena.out 中。
共输出 T 行,对于每组数据,设 Ai 为第 i(1 ≤ i ≤ m)组询问的答案,你只需要 输出一行包含一个整数,表示 (1 × A1) ⊕ (2 × A2) ⊕ · · · ⊕ (m × Am) 的结果。
【样例 1 输入】
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
【样例 1 输出】
5
19
7
1
【样例 1 解释】
共有 T = 4 组数据,这里只解释第一组。5 名选手的真实能力值为 [1, 0, 0, 2, 1]。5 组询问分别是对长度为 5, 4, 1, 2, 3 的前缀进行的。
1. 对于长度为 1 的前缀,由于只有 1 号一个人,因此答案为 1。
对于长度为 2 的前缀,由于 2 个人已经是 2 的幂次,因此不需要进行扩充。根据 抽签d1,1 = 1可知2号为擂主,由于a2 < 1,因此1号获胜,答案为1。
对于长度为 3 的前缀,首先 1 号、2 号比赛是 1 号获胜(因为 d1,1 = 1,故 2 号 为擂主,a2 < 1),然后虽然 4 号能力值还不知道,但 3 号、4 号比赛一定是 4 号 获胜(因为 d1,2 = 0,故 3 号为擂主,a3 < 1),而决赛 1 号、4 号谁获胜都有可 能(因为d2,1 = 1,故4号为擂主,如果a4 < 2则1号获胜,a4 ≥ 2则4号获 胜)。综上所述,答案为 1 + 4 = 5。
对于长度为 4 的前缀,我们根据上一条的分析得知,由于 a4 ≥ 2 ,所以决赛获 胜的是4 号。
对于长度为 5 的前缀,可以证明,可能获胜的选手包括 4 号、7 号、8 号,答案 为 19。
因此,该组测试数据的答案为(1×19)⊕(2×4)⊕(3×1)⊕(4×1)⊕(5×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。
【数据范围】
对于所有测试数据,保证:2 ≤ n,m ≤ 105,0 ≤ ai,Xj < 231,1 ≤ ci ≤ n,1 ≤ T ≤ 256。
特殊性质 A:保证询问的 ci 均为 2 的幂次。
特殊性质 B:保证所有的 dR,G = 0。