30370번 - Gacha 101 다국어

For each $i = 1, 2, \dots, N$, there are $A_i$ balls with $i$ written on them. These are put into a box and mixed up. The string variable $s$ consists of initially $N$ “0”s. Balls are taken out of the box one by one (uniformly at random and independently). When a ball with $i$ written on it is drawn, the $i$-th character of $s$ is changed to “1” (it remains unchanged if it was already “1”). Find the probability, modulo $998\,244\,353$, of having a point during this process that $s$ contains “101” as a contiguous substring.

The input consists of a single test case of the following format.

$N$

$A_1$ $A_2$ $\dots$ $A_N$

The first line consists of an integer $N$ between $1$ and $200\,000$, inclusive. The second line consists of $N$ positive integers $A_1, A_2, \dots , A_N$. For each $i$ ($1 \le i \le N$), $A_i$ represents the number of balls $i$ written. And they satisfy $\sum_{1 \le i \le N}{A_i} < 998\,244\,353$.

Output in a line the probability modulo $998\,244\,353$.

• How to find the probability modulo $998\,244\,353$
  • It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998\,244\,353$. Here, there is a unique $0 \le z < 998\,244\,353$ such that $y \equiv xz \pmod{998\,244\,353}$, so report this $z$.