P7738 [NOI2021] Quantum Communication

Due to differences in judging performance, the time limit for this problem is increased by 0.5 s.

Little Z is teaching himself knowledge about quantum computers. Recently, he has been studying the chapter on quantum communication and encountered an interesting problem. In this problem, Alice and Bob are doing quantum communication. Their communication language is a dictionary $S$ of size $n$. In this dictionary, each word $s_i$ ($1 \le i \le n$) can be represented by a $\boldsymbol{256}$-bit $\boldsymbol{01}$ string. In this problem, $s_i$ can be generated by calling the function `gen`. You can view it in `gen.cpp` under the problem directory. The parameters `n`, `a1`, and `a2` of this function will be given by the input. Alice and Bob will then communicate $m$ times. In each communication, Alice transmits **exactly one** word from the dictionary to Bob. However, the channel they use is unreliable and will be affected by noise. More specifically, for the $i$-th transmission, let the original word transmitted by Alice be $x_i$. This $01$ string will be affected by noise and have **at most** $\boldsymbol{k_i}$ **bits flipped**. In other words, let the $01$ string received by Bob this time be $y_i$. Compared with $x_i$, it may differ in up to $k_i$ bits, and $y_i$ may not appear in the dictionary $S$. At the same time, Bob learns that the bad guy Eve has also infiltrated their communication channel and is preparing to interfere with their communication. His method is to change the $01$ string received by Bob into an arbitrary $256$-bit $01$ string, and this string may not appear in the dictionary $S$. Eve is very cunning: he **does not necessarily** interfere with every communication. Now Bob asks you for help. For each upcoming communication, you need to determine, based on the final $01$ string received by Bob and the noise threshold $k_i$ ($0 \le k_i \le 15$) for this communication, whether it is possible that this communication was not interfered with by Eve (that is, the $01$ string received by Bob can be obtained by flipping at most $k_i$ bits of some word in the dictionary). If it is possible that Eve did not interfere, output $1$; otherwise output $0$. Bob trusts your ability very much, so you must answer **online**. See the input format for the specific requirements. To reduce input time, the string received by Bob will be given as a **length $\boldsymbol{64}$** hexadecimal string. The hexadecimal string contains digit characters $\texttt{0} \sim \texttt{9}$ and uppercase letters $\texttt{A} \sim \texttt{F}$, where $\texttt{A} \sim \texttt{F}$ represent the values $10 \sim 15$ respectively. A hexadecimal string can be converted bit by bit into a $01$ string. For example, `5` corresponds to `0101`, `A` corresponds to `1010`, and `C` corresponds to `1100`.

The first line contains four non-negative integers $n, m, a_1, a_2$, representing the dictionary size, the number of communications, and the initial values of parameters `a1` and `a2` in the `gen` function. You need to call the `gen` function mentioned in the description in your program to generate the dictionary. You may copy and use the code in `gen.cpp`. The boolean array `s[N+1][256]` in the program contains all words. In the next $m$ lines, each line contains a hexadecimal string of length $64$ and a non-negative integer $k_i$, representing the $01$ string finally received by Bob in the $i$-th communication and the noise threshold. To force contestants to **answer queries online**, after restoring the 256-bit $01$ string from the hexadecimal string, you must XOR each bit of the $01$ string with ${\mathit{lastans}}$ to obtain the real $01$ string received by Bob in this communication, where ${\mathit{lastans}} \in \{ 0, 1 \}$ is the answer to the previous query. Before the first query, ${\mathit{lastans}}$ is initialized to 0. Note: When using `scanf` and `printf` to read or output variables of type `unsigned long long`, the corresponding format specifier is `llu`.

Output $m$ lines. Each line contains an integer $0$ or $1$ indicating the answer to the current query.

**[Query Example]** To make the statement easier to explain, we give an example in a simplified setting by directly providing the words in the dictionary, reducing the word length to 4, and allowing offline queries. Consider a dictionary of size $n = 2$, with words `1010` and `0111`. For the query `B = 1011` and $k_1 = 1$, the answer should be $1$, because it can be obtained by flipping the 4-th bit of `1010` (from high to low bits, same below). For the query `1 = 0001` and $k_2 = 2$, the answer should be $1$, because it can be obtained by flipping the 2-nd and 3-rd bits of `0111`. For the query `1 = 0001` and $k_3 = 1$, the answer should be $0$. - By flipping at most 1 bit of `1010`, we can obtain `1010`, `0010`, `1110`, `1000`, `1011`. - By flipping at most 1 bit of `0111`, we can obtain `0111`, `1111`, `0011`, `0101`, `0110`. - We cannot obtain `1 = 0001`, so it must be caused by Eve’s interference. **[Constraints]** For all test points: $1 \le n \le 4 \times {10}^5$, $1 \le m \le 1.2 \times {10}^5$, $0 \le k_i \le 15$, and $a_1$ and $a_2$ are uniformly randomly generated in $[0, 2^{64} - 1]$. | Test Point ID | $n =$ | $m =$ | $k_i \le$ | Special Property | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $10$ | $2$ | None | | $2$ | $500$ | $500$ | $15$ | None | | $3$ | $1000$ | $1000$ | $0$ | None | | $4$ | $2000$ | $2000$ | $2$ | None | | $5$ | $5000$ | $5000$ | $15$ | None | | $6$ | $10^4$ | $10^4$ | $15$ | None | | $7$ | $2\times 10^4$ | $2\times 10^4$ | $15$ | None | | $8$ | $10^5$ | $10^5$ | $1$ | None | | $9$ | $4\times 10^5$ | $1.2\times 10^5$ | $1$ | None | | $10$ | $5\times 10^4$ | $5\times 10^4$ | $2$ | None | | $11$ | $7\times 10^4$ | $7\times 10^4$ | $3$ | None | | $12$ | $10^5$ | $10^5$ | $2$ | None | | $13$ | $3\times 10^4$ | $3\times 10^4$ | $5$ | None | | $14$ | $6\times 10^4$ | $6\times 10^4$ | $4$ | None | | $15$ | $1.2\times 10^5$ | $1.2\times 10^5$ | $5$ | None | | $16$ | $6\times 10^4$ | $6\times 10^4$ | $8$ | All query strings are generated randomly | | $17$ | $1.2\times 10^5$ | $1.2\times 10^5$ | $12$ | All query strings are generated randomly | | $18$ | $4\times 10^5$ | $10^5$ | $15$ | All query strings are generated randomly | | $19$ | $3\times 10^4$ | $3\times 10^4$ | $7$ | None | | $20$ | $6\times 10^4$ | $6\times 10^4$ | $9$ | None | | $21$ | $9\times 10^4$ | $9\times 10^4$ | $11$ | None | | $22$ | $2\times 10^5$ | $1.2\times 10^5$ | $12$ | None | | $23$ | $4\times 10^5$ | $8\times 10^4$ | $15$ | None | | $24$ | $4\times 10^5$ | $10^5$ | $15$ | None | | $25$ | $4\times 10^5$ | $1.2\times 10^5$ | $15$ | None | Translated by ChatGPT 5