P4564 [CTSC2018] Faceless

Zhenzhen is Lvlv’s good friend.

Zhenzhen likes to play a game called DotA (Defense of the Algorithm). In this game, Zhenzhen controls his hero and fights alongside teammates against another team. Zhenzhen’s favorite hero in DotA is called “Faceless,” and this hero has $2$ skills: - Lock: Cast on a specified enemy unit, dealing $1$ point of damage (reducing its health by $1$) with probability $p$. - Barrier: Cast on an area to trap all other units in that area so they cannot move. In the game, if a unit’s health drops to $0$ or below, that unit dies. Zhenzhen is not very skilled at controlling Faceless, so he decides to practice diligently. There are $n$ enemy units (numbered from $1$ to $n$), and the enemy unit numbered $i$ has $m_i$ health points. Zhenzhen has arranged a practice plan in which he will cast $Q$ skills in order: - For the Lock skill: Zhenzhen specifies an enemy unit $id$ and casts it on that unit. Since many factors determine the probability parameter $p$, the value of $p$ may be different each time. In particular, if the specified enemy unit is already dead, then this skill has no effect. - For the Barrier skill: Zhenzhen intends to cast it on $k$ specified enemy units, but since he is not good at casting this skill, he can hit exactly $1$ enemy unit. The probability of hitting each living enemy unit is equal (i.e., already dead enemy units have no effect). In particular, if all $k$ specified enemy units are already dead, then this skill also does not hit any unit. Now, Lvlv, who is watching Zhenzhen practice, wants to know: 1. For each Barrier skill that Zhenzhen casts, what is the probability that it hits each enemy, respectively. 2. After all of Zhenzhen’s skills have been cast, what is the expected remaining health of each enemy unit. To prevent precision errors, for all numerical outputs, please output their values modulo $998244353$. Since Barrier is Faceless’s ultimate skill, the number of times Zhenzhen casts it will not be too many. See Constraints.

The $1$-st line contains $1$ positive integer $n$, the number of enemy units. The $2$-nd line contains $n$ positive integers $m_1, \cdots, m_n$, representing the initial health of each enemy unit in order. The $3$-rd line contains $1$ non-negative integer $Q$, the number of skills Zhenzhen will cast. The $4$-th to the $(Q + 3)$-rd lines each describe one skill; the $(i + 3)$-rd line describes the $i$-th skill. Each line begins with an integer $op$, indicating the type of the skill. If $op = 0$, it indicates the Lock skill. This is followed by $3$ positive integers $id, u, v$, meaning the target is $id$, and the hit probability is $p = \frac{u}{v}$. (Guaranteed that $1 \le id \le n$, $0 < u \le v < 998244353$.) If $op = 1$, it indicates the Barrier skill. This is followed by $1$ positive integer $k$ indicating the number of targets, then an additional $k$ numbers $id_1, \cdots, id_k$ describing all the targets of this skill. (Guaranteed that all $1 \le id_i \le n$ are pairwise distinct.) Within each line, if there are multiple numbers, separate them with a single space.

Output $C + 1$ lines (where $C$ is the number of Barrier skills): For the first $C$ lines, corresponding to each Barrier skill in order: Output $k$ numbers. The $i$-th number is the probability that the Barrier hits enemy unit $id_i$. On the $(C + 1)$-st line, output $n$ numbers. The $i$-th number is the expected remaining health of enemy unit $i$ after all skills have been cast. Within each line, if there are multiple numbers, separate them with a single space. For all numerical values, output them modulo $998244353$: that is, suppose the answer in reduced fraction form is $\frac{a}{b}$ with $\gcd(a, b) = 1$. Output the integer $x$ such that $b x \equiv a \bmod 998244353$ and $0 \le x < 998244353$. (It can be proven that such an integer $x$ is unique.)

Sample Explanation 1 Zhenzhen casts the following skills in order: 1. Cast Lock on enemy unit $2$: deals $1$ damage with probability $1$. At this moment, enemy unit $2$ must have $1$ health remaining. 2. Cast Barrier on enemy unit $2$: (since enemy unit $2$ is still alive,) it must hit unit $2$. 3. Cast Lock on enemy unit $2$: deals $1$ damage with probability $1$. 4. Cast Lock on enemy unit $3$: deals $1$ damage with probability $1$. Now the three enemy units’ health values must be $1, 0, 2$ respectively, and enemy unit $2$ must be dead. 5. Cast Barrier on enemy unit $2$: (since enemy unit $2$ is dead,) it must hit no unit. 6. Cast Barrier on enemy units $1, 2, 3$: the probabilities of hitting enemy units $1$ and $3$ are equal, i.e., each $\frac{1}{2}$. Finally, the remaining health of the three enemy units must be $1, 0, 2$. Sample Explanation 2 Analysis for each Barrier skill: 1. The $1$-st Barrier (targets enemy units $1, 2$): - The probability that enemy unit $2$ is alive is $\frac{1}{2}$, and enemy unit $1$ must be alive. - If enemy unit $2$ is alive, then the probabilities of Barrier hitting $1$ and $2$ are equal, both $\frac{1}{2}$; if enemy unit $2$ is dead, then Barrier must hit enemy unit $1$. - Therefore: the probability of hitting enemy unit $1$ is $\frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}$; the probability of hitting enemy unit $2$ is $\frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$. 2. The $2$-nd Barrier (targets enemy units $1, 2, 3$): - The probabilities that the three enemy units are alive are $1, \frac{1}{2}, \frac{1}{3}$, respectively. - The probability that $1, 2, 3$ are all alive is $\frac{1}{6}$; the probability that only $1, 2$ are alive is $\frac{1}{3}$; the probability that only $1, 3$ are alive is $\frac{1}{6}$; the probability that only $1$ is alive is $\frac{1}{3}$. - Therefore: the probability of hitting enemy unit $1$ is $\frac{1}{6} \times \frac{1}{3} + (\frac{1}{3} + \frac{1}{6}) \times \frac{1}{2} + \frac{1}{3} \times 1 = \frac{23}{36}$; the probability of hitting enemy unit $2$ is $\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}$; the probability of hitting enemy unit $3$ is $\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}$. Finally, the expected remaining health of the three enemy units is $1, \frac{1}{2}, \frac{1}{3}$. Constraints Let $C$ be the number of Barrier skills. Test point id|n =|Q =|C =|u, v|Other constraints -|-|-|-|-|- 1|5|21|6|u < v|None 2|60|199992|500|u < v|All $p$ are equal 3|60|23|6|u < v|All $m_i = 1$ 4|60|199994|500|u < v|None 5|60|199995|500|u < v|None 6|60|199996|0|u < v|None 7|60|199997|500|u = v|None 8|200|199998|1000|u < v|None 9|200|199999|1000|u < v|None 10|200|200000|1000|u < v|None For all test points, it is guaranteed that $n \le 200$, $Q \le 200000$, $C \le 1000$, $m_i \le 100$. Hint The units digit of $Q$ can help you quickly determine the test point id. The test point order may not correlate with difficulty. Thanks to @和泉正宗 for providing the statement. Translated by ChatGPT 5