UOJ Logo Universal Online Judge

UOJ

#676. 【NOI2021】量子通信

附件下载 统计

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

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 对应 0101A 对应 1010C 对应 1100

注:$16$ 进制串 AB 对应的 $01$ 串是 10101011,其中第 $1$(下标从 $0$ 开始)个字符为 0

输入格式

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

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

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

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

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

输出格式

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

示例

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

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

对于询问 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$ 位可得 10100010111010001011
  • 翻转 0111 至多 $1$ 位可得 01111111001101010110
  • 无法得到 1 = 0001,它必定是由 Eve 干扰得到的。

样例一、样例二、样例三

见样例数据下载。

数据范围

对于所有测试点:$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]$ 之间均匀随机生成。

测试点编号 $n =$ $m =$ $k_i \le$ 特殊性质
$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$

时间限制:$\require{cancel}\cancel{\texttt{2s}}\texttt{3s}$

空间限制:$\texttt{384MB}$