P6125 [JSOI2009] Interesting Game

Xiao Yangyang invented an interesting game: there are $n$ players, and each player has a letter sequence of length $l$. Any two players' letter sequences are different. There are $m$ different letters in total, and all sequences are made up of these $m$ letters. For convenience, we use the first $m$ uppercase letters. For example, when $m=3,l=4$, $\texttt{ABAA}$ and $\texttt{CBCA}$ are two valid sequences. Now Xiao Yangyang controls a magical machine. At each moment, the machine randomly generates one letter, and the probability that the $i$-th letter is generated is $\dfrac{p_i}{q_i}$. Obviously, $\sum \limits_{k=1}^m \dfrac{p_i}{q_i}=1$. After $T$ moments, the machine will generate a letter sequence of length $T$. If at some moment a player finds that their letter sequence appears in the sequence generated by the machine, where “appears” means the player's sequence is a continuous substring of the machine's sequence, then we say this player wins and the game ends. Now Xiao Yangyang is interested in this question: what is the probability that each player wins this game?

The first line contains three positive integers $n,l,m$, meaning there are $n$ people, each letter sequence has length $l$, and there are $m$ letters in total. The next $m$ lines each contain two non-negative integers $p, q$, meaning the probability of randomly getting the $i$-th letter is $\frac{p}{q}$. The next $n$ lines each contain a letter sequence of length $l$, representing the $i$-th person's letter sequence.

Output $n$ lines. Each line contains one real number, representing the probability that the $i$-th person wins. Round the output to two decimal places.

Constraints: $1 \leq n,l,m \leq 10$, $0 \leq p_i \leq q_i \leq 10$ and $\gcd(p,q) = 1$。 Translated by ChatGPT 5