【NOI2021】量子通信 - 题目 - Universal Online Judge

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

Alice 和 Bob 接下来要进行 $m$ 次通信，每次通信由 Alice 向 Bob 传输恰好一个字典中的单词。然而，两人使用的通信信道并不可靠，会受到噪音的干扰。更具体地，对于第 $i$ 次传输，记 Alice 传输的原单词为 $x_{i}$ ，该 $01$ 串会受噪音干扰而翻转最多 $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 \leq k_{i} \leq 15$ ），判断这次通信是否有可能没有受到 Eve 的干扰（即 Bob 收到的 $01$ 串可以由字典中的某个单词翻转至多 $k_{i}$ 位后得到）。本次通信如果有可能没受到 Eve 干扰，请你输出 $1$ ，否则输出 $0$ 。Bob 很信任你的能力，所以你需要在线地回答结果，具体要求见输入格式。

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

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

注： $16$ 进制串 AB 对应的 $01$ 串是 10101011，其中第 $1$ （下标从 $0$ 开始）个字符为 0。

输入格式

输入数据第一行包含四个非负整数 $n, m, a_{1}, a_{2}$ ，分别表示字典大小，通信次数，以及 gen 函数中参数 a1 和 a2 的初始值。

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

接下来 $m$ 行，每行包含一个长度为 $64$ 的 $16$ 进制串和一个非负整数 $k_{i}$ ，分别表示第 $i$ 次通信 Bob 最终收到的 $01$ 串和噪音干扰阈值。

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

注意：使用 scanf 和 printf 函数读入或输出 unsigned long long 类型变量时，对应的占位符为 llu。

输出格式

输出共 $m$ 行，每行一个整数 $0$ 或 $1$ 表示当前询问的答案。

示例

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

考虑字典大小为 $n = 2$ ，单词有 1010 和 0111。

对于询问 B = 1011 和 $k_{1} = 1$ ，回答应该是 $1$ ，通过翻转 1010 的第 $4$ 位（从高位到低位，下同）得到。

对于询问 1 = 0001 和 $k_{2} = 2$ ，回答应该是 $1$ ，通过翻转 0111 的第 $2$ 、 $3$ 位得到。

对于询问 1 = 0001 和 $k_{3} = 1$ ，回答应该是 $0$ 。

翻转 1010 至多 $1$ 位可得 1010、0010、1110、1000、1011。
翻转 0111 至多 $1$ 位可得 0111、1111、0011、0101、0110。
无法得到 1 = 0001，它必定是由 Eve 干扰得到的。

样例一、样例二、样例三

见样例数据下载。

数据范围

对于所有测试点： $1 \leq n \leq 4 \times 10^{5}$ ， $1 \leq m \leq 1.2 \times 10^{5}$ ， $0 \leq k_{i} \leq 15$ ， $a_{1}$ 和 $a_{2}$ 在 $[0, 2^{64} - 1]$ 之间均匀随机生成。

测试点编号	$n =$	$m =$	$k_{i} \leq$	特殊性质
$1$	$10$	$10$	$2$	无
$2$	$500$	$500$	$15$	无
$3$	$1000$	$1000$	$0$	无
$4$	$2000$	$2000$	$2$	无
$5$	$5000$	$5000$	$15$	无
$6$	$10000$	$10000$	$15$	无
$7$	$20000$	$20000$	$15$	无
$8$	$100000$	$100000$	$1$	无
$9$	$400000$	$120000$	$1$	无
$10$	$50000$	$50000$	$2$	无
$11$	$70000$	$70000$	$3$	无
$12$	$100000$	$100000$	$2$	无
$13$	$30000$	$30000$	$5$	无
$14$	$60000$	$60000$	$4$	无
$15$	$120000$	$120000$	$5$	无
$16$	$60000$	$60000$	$8$	所有询问串随机生成
$17$	$120000$	$120000$	$12$	所有询问串随机生成
$18$	$400000$	$100000$	$15$	所有询问串随机生成
$19$	$30000$	$30000$	$7$	无
$20$	$60000$	$60000$	$9$	无
$21$	$90000$	$90000$	$11$	无
$22$	$200000$	$120000$	$12$	无
$23$	$400000$	$80000$	$15$	无
$24$	$400000$	$100000$	$15$	无
$25$	$400000$	$120000$	$15$	无

时间限制： $2 s 3 s$

空间限制： $384 MB$

Universal Online Judge

UOJ

#676. 【NOI2021】量子通信

输入格式

输出格式

示例

样例一、样例二、样例三

数据范围