P7738 [NOI2021] 量子通信 做题记录

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

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

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

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

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

$16$ 进制串可以逐位转化为 $01$ 串，例如：5 对应 0101，A 对应 1010，C 对应 1100。

$1 \le n \le 4 \times {10}^5$，$1 \le m \le 1.2 \times {10}^5$，$0 \le k_i \le 15$，$a_1$ 和 $a_2$ 在 $[0, 2^{64} - 1]$ 之间均匀随机生成。

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

由于数据随机，字典中合法的串的个数大概只有 $400000\div2^{16}\times16$ 个，这个数字大概是 $100$，所以能过。