[NOI2021] 量子通信

题目背景

由于评测性能差异，本题时限 +0.5s。

题目描述

小 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。

输入格式

输入数据第一行包含四个非负整数 \(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\) 串每一位异或上 \({\mathit{lastans}}\) 才能得到这次通信中 Bob 收到的真实 \(01\) 串，其中 \({\mathit{lastans}} \in \{ 0, 1 \}\) 表示上一次询问的答案，第一个询问前 \({\mathit{lastans}}\) 初始值为 0。

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

输出格式

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

样例 #1

样例输入 #1

见附件中的 qi/qi1.in

样例输出 #1

见附件中的 qi/qi1.ans

样例 #2

样例输入 #2

见附件中的 qi/qi2.in

样例输出 #2

见附件中的 qi/qi2.ans

样例 #3

样例输入 #3

见附件中的 qi/qi3.in

样例输出 #3

见附件中的 qi/qi3.ans

提示

【询问举例】

为了方便解释题意，我们使用了直接给出字典中单词、缩小单词长度为 \(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 \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\)	\(10^4\)	\(10^4\)	\(15\)	无
\(7\)	\(2\times 10^4\)	\(2\times 10^4\)	\(15\)	无
\(8\)	\(10^5\)	\(10^5\)	\(1\)	无
\(9\)	\(4\times 10^5\)	\(1.2\times 10^5\)	\(1\)	无
\(10\)	\(5\times 10^4\)	\(5\times 10^4\)	\(2\)	无
\(11\)	\(7\times 10^4\)	\(7\times 10^4\)	\(3\)	无
\(12\)	\(10^5\)	\(10^5\)	\(2\)	无
\(13\)	\(3\times 10^4\)	\(3\times 10^4\)	\(5\)	无
\(14\)	\(6\times 10^4\)	\(6\times 10^4\)	\(4\)	无
\(15\)	\(1.2\times 10^5\)	\(1.2\times 10^5\)	\(5\)	无
\(16\)	\(6\times 10^4\)	\(6\times 10^4\)	\(8\)	所有询问串随机生成
\(17\)	\(1.2\times 10^5\)	\(1.2\times 10^5\)	\(12\)	所有询问串随机生成
\(18\)	\(4\times 10^5\)	\(10^5\)	\(15\)	所有询问串随机生成
\(19\)	\(3\times 10^4\)	\(3\times 10^4\)	\(7\)	无
\(20\)	\(6\times 10^4\)	\(6\times 10^4\)	\(9\)	无
\(21\)	\(9\times 10^4\)	\(9\times 10^4\)	\(11\)	无
\(22\)	\(2\times 10^5\)	\(1.2\times 10^5\)	\(12\)	无
\(23\)	\(4\times 10^5\)	\(8\times 10^4\)	\(15\)	无
\(24\)	\(4\times 10^5\)	\(10^5\)	\(15\)	无
\(25\)	\(4\times 10^5\)	\(1.2\times 10^5\)	\(15\)	无

如何迅速判断一个串是否符合要求？显然bitset

那么我们可以找到所有的有可能成为答案的串，一一判断

随机数据，如果是固定了整个串的某几位，那么期望情况下，可选的答案会少很多。

\(k\le15\)，如果存在符合要求的串，那么这个串的大多数位置都是和给的串是一样的。但是仍然没有办法找到一些一定一样的串来减少位置。注意到 \(15<\sqrt{256}\)，我们可以把整个询问串分成16个长度为16的串，根据抽屉原理，集合中一个满足要求的串，一定存在某一块串是和询问串串是相同的。那么串的集合中这一块串和询问串这一块相等的期望串数量有 \(\frac{n}{2^{16}}\) 个。我们回答一次询问的复杂度就是 \(\frac{n}{2^{16}}\times 16\times \frac{256}{\omega}\)，可过。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=4e5+1,M=2e5+1;
ull a1,a2;
char str[256];
bitset<256> s[N],p;
int lst,n,m,k;
ull myRand(ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void gen(int n, ull a1, ull a2) {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 256; j++)
            s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}
vector<int>g[16][1<<16];
int main() {
	scanf("%d%d%llu%llu",&n,&m,&a1,&a2);
	gen(n,a1,a2);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<16;j++)
		{
			int s=0;
			for(int k=0;k<16;k++)
				s|=::s[i][j<<4|k]<<k;
			g[j][s].push_back(i);
		}
	}
	while(m--)
	{
		scanf("%s%d",str,&k);
		for(int j=0;j<256;j+=4){	
			int s=str[j>>2];
			if(s<58)
				s-=48;
			else
				s=s-'A'+10;
			p[j]=(s>>3&1)^lst;
			p[j+1]=(s>>2&1)^lst;
			p[j+2]=(s>>1&1)^lst;
			p[j+3]=(s&1)^lst;
		}
		lst=0;
		for(int i=0;i<16;i++)
		{
			int s=0;
			for(int j=0;j<16;j++)
				s|=p[i<<4|j]<<j;
			for(int j=0;j<g[i][s].size();j++)
				if((p^::s[g[i][s][j]]).count()<=k)
					lst=1,j=1000000000;
			if(lst)
				break;
		}
		putchar(lst+48),puts("");
	}
    return 0;
}