P5405 [CTS2019] Pay-to-Win Mobile Gacha Game

Student Xiao Liu is a boy who likes pay-to-win mobile games. He recently got addicted to a new game whose content is to keep drawing cards. It is known that: - There are $N$ types of cards in the pool. The $i$-th type of card has a weight $W_i$. Xiao Liu does not know the exact value of $W_i$, but by talking with other players he learned that $W_i$ follows a distribution. - Specifically, for each $i$, Xiao Liu knows three parameters $p_{i,1}, p_{i,2}, p_{i,3}$. The value of $W_i$ is $j$ with probability $p_{i,j}$. It is guaranteed that $p_{i,1} + p_{i,2} + p_{i,3} = 1$. Xiao Liu starts playing the game. Each time, he pays 1 yuan to draw one card. The probability of drawing card $i$ is: $$\frac{W_i}{\sum_j W_j}$$ Xiao Liu will keep drawing cards **until** he has collected all $N$ types of cards. After the drawing ends, the server records the time $T_i$ when Xiao Liu gets each card for the **first time**. The game company sets up an easter egg: the company prepares $N - 1$ ordered pairs $(u_i, v_i)$. If for every $i$, the condition $T_{u_i} < T_{v_i}$ holds, then the company will consider Xiao Liu extremely lucky and will give him a cabinet of figurines as the lucky grand prize. To reduce the chance of winning, these $(u_i, v_i)$ satisfy the following property: for any $\varnothing \ne S \subsetneq \{1,2,\ldots,N\}$, there always exists some $(u_i, v_i)$ such that $u_i \in S, v_i \notin S$ **or** $u_i \notin S, v_i \in S$. Please compute the probability that Xiao Liu can get the lucky grand prize. It is guaranteed that the result is a rational number. Output the result modulo $998244353$.

The first line contains an integer $N$, the number of card types. The next $N$ lines each contain three integers $a_{i,1}, a_{i,2}, a_{i,3}$, and the probabilities in the statement are given by $p_{i,j} = \frac{a_{i,j}}{a_{i,1} + a_{i,2} + a_{i,3}}$. The next $N - 1$ lines each contain two integers $u_i, v_i$, describing an ordered pair (see the statement for its meaning).

Output one integer in one line, the required probability modulo $998244353$.

#### Explanation of Sample 1 $W_2$ is $1$ or $2$ with probability $\frac 12$: - If $W_2 = 1$, then the probability that $T_1 < T_2$ is $\frac 34$. - Otherwise, if $W_2 = 2$, then the probability that $T_1 < T_2$ is $\frac 35$. Combining all cases, the answer is $\frac 12\left(\frac 34 + \frac 35\right) = \frac{27}{40}$. You can verify that its value modulo $998244353$ is indeed the given output. #### Testdata Constraints For all testdata, it is guaranteed that $N \le 1000$ and $a_{i,j} \le 10^6$. - $20$ points: $N \le 15$. - $15$ points: $N \le 200$, and every constraint satisfies $|u_i−v_i|=1$. - $20$ points: $N \le 1000$, and every constraint satisfies $|u_i−v_i|=1$. - $15$ points: $N \le 200$. - $30$ points: no special constraints. Translated by ChatGPT 5