25068번 - Quantum Communication 다국어

Alice and Bob are engaging in quantum communication. Their language of communication is a dictionary $S$ of size $n$. In the dictionary, a word $s_i$ $(1 \le i \le n)$ may be represented by a 256-bit binary string. In this problem, $s_i$ may be generated by calling function gen. The contestants may refer to gen.cpp, and the parameters n,a1,a2 will be specified by the test cases.

Alice and Bob will communicate for $m$ rounds next. In each round, Alice will send bob exactly one word in the dictionary. However, their communication channel is not reliable and may be disturbed by noise. More formally, for the $i$-th round of communication, suppose the word Alice wants to send is $x_i$, then at most $k_i$ bits of the binary string will flip. In other words, suppose the binary string Bob receives is $y_i$, then $y_i$ is different from $x_i$ for at most $k_i$ positions. $y_i$ does not have to be in dictionary $S$.

At the same time, Bob knows Eve has invaded the communication channel and is going to manipulate the communication between Alice and Bob. Eve will replace the binary string Bob is going into receive with an arbitrary 256-bit binary string, and the arbitrary 256-bit binary string does not have to be in the dictionary. Eve does not have to manipulate all rounds of communication.

Now Bob asks you for help, and you need to determine whether it is possible that a round of communication is not manipulated by Eve given the string Bob received and the threshold for noise disturbance $k_i$ $(0 \le k_i \le 15)$. In other words, you need to check whether the binary string Bob received can be obtained by flipping at most $k_i$ bits of a word in the dictionary. If it is possible that the round of communication is not manipulated by Eve, output 1. Otherwise, output 0. Bob trusts your ability, so you need to answer the queries online. For the specifics, see the input section.

To save the time spent on I/O, the strings Bob received are given by 64-bit hexadecimal strings. The hexadecimal strings contain numerals 0-9 and upper-case English letters A-F. A-F represents 10-15 in that order. A hexadecimal string may be converted to a binary string bit by bit. For example, 5 will correspond to 0101, A will correspond to 1010, and C will correspond to 1100.

The first line of the input contains four nonnegative integers $n,m,a_1,a_2$ denoting the size of the dictionary, the number of rounds of communication, and the initial values of parameters a1 and a2 for the function gen. Contestants need to generate the dictionary using the gen function mentioned in the problem statement. Contestants may copy and use the code in gen.cpp. The Boolean array s[N+1][256] is just the list of all words.

For the next $m$ lines, each line contains a hexadecimal string of length 64 and a nonnegative integer $k_i$ denoting the final binary string Bob received in round $i$ and the threshold for noise disturbance.

To make sure contestants are answering the queries online, after the contestants recover the 256-bit binary string based on the hexadecimal string, contestants need to perform XOR operation with lastans bitwise to recover the real binary string Bob received in the round. lastans $\in \{0,1\}$ denotes the answer to the query last round. Before the first round, the initial value of lastans is 0.

Notice: when reading or writing unsigned long long variables using scanf or printf, use llu.

The output consists of $m$ lines. Each line contains an integer 0 or 1 denoting the answer to the query.

For all test cases, $1 \le n \le 4 \times 10^5$, $1 \le m \le 1.2 \times 10^5$, $0 \le k \le 15$, and $a_1,a_2$ are uniformly random among $[0,2^{64}-1]$.

For convenience, we will give the words in the dictionary explicitly, reduce the word length to 4, and allow offline answers to the queries.

Suppose the dictionary size is $n = 2$. The words are 1010 and 0111.

For query B = 1011 and $k_1 = 1$, the output shall be 1 since B may be obtained by flipping the 4-th bit of 1010.

For query B = 0001 and $k_2 = 2$, the output shall be 1 since 0001 may be obtained by flipping the second and the third bit of 0111.

For query B = 0001 and $k_3 = 1$, the output shall be 0.

The remaining samples can be found here.