P7738 [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

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] 之间均匀随机生成。

观察到由于最多只会翻转 1515 位,所以可以把每个 0101 串都分成 1616 段,这样若没被那个人干扰则总会有一段和字典中的完全一样。

由于数据随机,字典中合法的串的个数大概只有 400000÷216×16400000\div2^{16}\times16 个,这个数字大概是 100100,所以能过。