#1857. 「NOI2021」量子通信

「NOI2021」量子通信

题目描述

小 Z 正在自学量子计算机相关知识,最近他在研究量子通信章节,并遇到了一个有趣的问题。在该问题中,Alice 和 Bob 正在进行量子通信,它们的通信语言是一个大小为 nn 的字典 SS,在该字典中,每一个单词 sis_i1in1 \le i \le n)都可以用一个 256\boldsymbol{256} 位的 01\boldsymbol{01} 来表示。在本题中 sis_i 可以通过调用函数 gen 来生成,选手可以在题目目录下的 gen.cpp 中查看,该函数的参数 na1a2 将由输入数据给出。

Alice 和 Bob 接下来要进行 mm 次通信,每次通信由 Alice 向 Bob 传输恰好一个字典中的单词。然而,两人使用的通信信道并不可靠,会受到噪音的干扰。更具体地,对于第 ii 次传输,记 Alice 传输的原单词为 xix_i,该 0101 串会受噪音干扰而翻转最多 ki\boldsymbol{k_i} 。换句话说,记 Bob 这次收到的 0101 串为 yiy_i,它与 xix_i 相比,可能有最多 kik_i 位是不同的,并且 yiy_i 可能不在字典 SS 中出现。

与此同时,Bob 得知坏人 Eve 也潜入了两人的通信信道,并准备干扰两人的通信。他的干扰方式是将 Bob 收到的 0101 串变为任意的 2562560101 串,并且这个串可能不在字典 SS 中出现。Eve 非常狡猾,他不一定会对每次通信都进行干扰。

现在 Bob 找来了你帮忙,对于接下来的每次通信,你需要根据 Bob 最终收到的 0101 串以及这次通信的噪音干扰阈值 kik_i0ki150 \le k_i \le 15),判断这次通信是否有可能没有受到 Eve 的干扰(即 Bob 收到的 0101 串可以由字典中的某个单词翻转至多 kik_i 位后得到)。本次通信如果有可能没受到 Eve 干扰,请你输出 11,否则输出 00。Bob 很信任你的能力,所以你需要在线地回答结果,具体要求见输入格式

为了降低读入用时, Bob 收到的串将用长度为 64\boldsymbol{64} 16\boldsymbol{16} 进制串给出,1616 进制串中包含数字字符 09\texttt{0} \sim \texttt{9} 与大写英文字母 AF\texttt{A} \sim \texttt{F},其中字符 AF\texttt{A} \sim \texttt{F} 依次表示数值 101510 \sim 15

1616 进制串可以逐位转化为 0101 串,例如:5 对应 0101A 对应 1010C 对应 1100

输入格式

输入数据第一行包含四个非负整数 n,m,a1,a2n, m, a_1, a_2,分别表示字典大小,通信次数,以及 gen 函数中参数 a1a2 的初始值。

选手需要在自己的程序中调用题目描述中提到的 gen 函数生成单词表,选手可以复制并使用 gen.cpp 中的代码,程序中的布尔数组 s[N+1][256] 即为所有的单词。

接下来 mm 行,每行包含一个长度为 64641616 进制串和一个非负整数 kik_i,分别表示第 ii 次通信 Bob 最终收到的 0101 串和噪音干扰阈值。

为了强制选手在线地回答询问,选手根据 1616 进制串还原出 2562560101 串后,将 0101 串每一位异或上 lastans{\mathit{lastans}} 才能得到这次通信中 Bob 收到的真实 0101 串,其中 lastans{0,1}{\mathit{lastans}} \in \{ 0, 1 \} 表示上一次询问的答案,第一个询问前 lastans{\mathit{lastans}} 初始值为 0。

注意:使用 scanfprintf 函数读入或输出 unsigned long long 类型变量时,对应的占位符为 llu

输出格式

输出共 mm 行,每行一个整数 0011 表示当前询问的答案。

询问举例

为了方便解释题意,我们使用了直接给出字典中单词、缩小单词长度为 44、允许离线地回答询问等方式,对简化的情况举例。

考虑字典大小为 n=2n = 2,单词有 10100111

对于询问 B = 1011k1=1k_1 = 1,回答应该是 11,通过翻转 1010 的第 44 位(从高位到低位,下同)得到。

对于询问 1 = 0001k2=2k_2 = 2,回答应该是 11,通过翻转 0111 的第 2233 位得到。

对于询问 1 = 0001k3=1k_3 = 1,回答应该是 00

  • 翻转 1010 至多 11 位可得 10100010111010001011
  • 翻转 0111 至多 11 位可得 01111111001101010110
  • 无法得到 1 = 0001,它必定是由 Eve 干扰得到的。

样例 1

见附加文件中的 qi/qi1.inqi/qi1.ans

样例 2

见附加文件中的 qi/qi2.inqi/qi2.ans

样例 3

见附加文件中的 qi/qi3.inqi/qi3.ans

数据范围与提示

对于所有测试点:1n4×1051 \le n \le 4 \times {10}^51m1.2×1051 \le m \le 1.2 \times {10}^50ki150 \le k_i \le 15a1a_1a2a_2[0,2641][0, 2^{64} - 1] 之间均匀随机生成。

测试点编号 n=n = m=m = kik_i \le 特殊性质
11 1010 22
22 500500 1515
33 10001000 00
44 20002000 22
55 50005000 1515
66 1000010000
77 2000020000
88 100000100000 11
99 400000400000 120000120000
1010 5000050000 22
1111 7000070000 33
1212 100000100000 22
1313 3000030000 55
1414 6000060000 44
1515 120000120000 55
1616 6000060000 88 所有询问串随机生成
1717 120000120000 1212
1818 400000400000 100000100000 1515
1919 3000030000 77
2020 6000060000 99
2121 9000090000 1111
2222 200000200000 120000120000 1212
2323 400000400000 8000080000 1515
2424 100000100000
2525 120000120000