P9379 [THUPC 2023 Finals] Slot Machine

Xiao I runs an arcade, and a new type of slot machine has recently become very popular. As the operator, Xiao I first needs to set the state of the slot machine. The state is a triple $(l,S,\mathbf{p})$, where: - $l$ is a positive integer. - $S$ is a non-empty set of strings, where every string is a length-$l$ binary string. - $\mathbf{p}$ is a length-$l$ real sequence $p_0,p_1,\dots,p_{l-1}$, where for any $0 \le i \le l - 1$, $0 < p_i \le 1$. After setting the state, the game can start. Each round of the game works as follows: - The player first obtains the slot machine state $(l,S,\mathbf{p})$. - Internally, the slot machine chooses a string $s \in S$ as the answer string. The player needs to obtain the answer string through several interactions with the machine. - In each interaction, the player inserts one coin and pulls the lever. Then the machine displays an information string $t$ of length $l$. For $0 \le i \le l - 1$, $t_i$ equals $s_i$ with probability $p_i$, and equals `?` with probability $(1-p_i)$. - All random processes used to generate information strings during interactions are pairwise independent. - Once the player can uniquely determine the answer string based on **the slot machine state and the information strings obtained from interactions**, they may input the answer string into the machine to end the game and receive the reward. Xiao I has set a state, but has not decided how large the reward should be. To match the reward with the difficulty, Xiao I wants to know: for each string $t$ in $S$, if the player plays with an optimal strategy (that is, they end the game as soon as the answer string can be uniquely determined), and the answer string is $t$, what is the expected number of coins the player needs to insert. Since Xiao I does not like real numbers, you need to output the answer modulo $998244353$.

**This problem has multiple test cases.** The first line contains an integer $T$ indicating the number of test cases, followed by the input for each test case. For each test case: - The first line contains two integers $l,n$, denoting the string length and the size of $S$. - The second line contains $l$ integers $c_0,c_1,\dots,c_{l-1}$, where $p_i = \frac{c_i}{10^4}$. - The next $n$ lines each contain a length-$l$ binary string $s_i$, describing a string in $S$.

For each test case, output $n$ lines. The $i$-th line should be the expected number of coins the player needs to insert when the answer string is $s_i$ under the optimal strategy, modulo $998244353$. The problem guarantees that this value always exists in the modular sense.

**[Sample Explanation #1]** - For the first test case, in each interaction there is a probability of $\frac{5000}{10000} = \frac{1}{2}$ to know whether the answer string is $0$ or $1$, and a probability of $\frac{1}{2}$ to obtain no information. Therefore the expected number of coins is $\sum_{i=1}^{+\infty} \frac{i}{2^i} = 2$. - For the second test case, in each interaction you can always obtain the second bit of the string, and you obtain the first bit with probability $\frac{1}{10000}$. When the second string is the answer string, it can be uniquely determined by the second bit, while for the other two strings, you must obtain the first bit. - For the third test case, since $|S| = 1$, no interaction is needed to determine the answer string. - For the fourth test case, I have a brilliant explanation, but this space is too small to write it down. **[Constraints]** For all testdata, $1 \le T \le 10$, $1 \le l \le 15$, $1 \le n \le 2^l$, $1 \le c_i \le 10^4$, and $s_1,\dots,s_n$ are pairwise distinct length-$l$ binary strings. **[Afterword]** “Hey, hey, hey, minors are not allowed to enter the arcade! What? You say you want to go in to learn competitive programming algorithms? Who would believe that nonsense!” **[Source]** From the finals of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2023). Solutions and other resources can be found at [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023). Translated by ChatGPT 5