Beautiful Mirrors
Contest: Codeforces Round 604 (Div. 2)
Difficulty rating: 2100
Tags: data structures, dp, math, probabilities

Creatnx has $$$n$$$ mirrors, numbered from $$$1$$$ to $$$n$$$. Every day, Creatnx asks exactly one mirror "Am I beautiful?". The $$$i$$$-th mirror will tell Creatnx that he is beautiful with probability $$$\frac{p_i}{100}$$$ for all $$$1 \le i \le n$$$.

Creatnx asks the mirrors one by one, starting from the $$$1$$$-st mirror. Every day, if he asks $$$i$$$-th mirror, there are two possibilities:

- The $$$i$$$-th mirror tells Creatnx that he is beautiful. In this case, if $$$i = n$$$ Creatnx will stop and become happy, otherwise he will continue asking the $$$i+1$$$-th mirror next day;
- In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the $$$1$$$-st mirror again.

You need to calculate the expected number of days until Creatnx becomes happy.

This number should be found by modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of mirrors.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq 100$$$).

Output format:
Print the answer modulo $$$998244353$$$ in a single line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, there is only one mirror and it tells, that Creatnx is beautiful with probability $$$\frac{1}{2}$$$. So, the expected number of days until Creatnx becomes happy is $$$2$$$.

Example input:
1
50

Example output:
2

Example input:
3
10 20 50

Example output:
112

Editorial:
Let $$$p_i$$$ be the probability that the $$$i$$$-th mirror will answer YES when it is asked. That is, this $$$p_i$$$ equals to $$$p_i$$$ in the problem statement divide by 100.
Let $$$e_i$$$ be the expected number of days until Creatnx becomes happy when initially he is at the $$$i$$$-th mirror. For convenient, let $$$e_{n+1} = 0$$$ (because when Creatnx is at $$$(n+1)$$$-th mirror he is happy already). The answer of the problem will be $$$e_1$$$.
By the definition of expectation value and its basic properties, the following must holds for all $$$1 \leq i \leq n$$$:
Let explain this equation for those who are not familiar with probability. Expectation value is just average of all possible outcomes. The first number 1 in the right hand side means Creatnx spends 1 day to ask the $$$i$$$-th mirror. With probability of $$$p_i$$$ the $$$i$$$-th mirror will answer YES and Creatnx will move to the $$$(i+1)$$$-th mirror in the next day. At the $$$(i+1)$$$-th mirror, Creatnx on average needs to spend $$$e_{i+1}$$$ days more to become happy. The second term $$$p_i \cdot e_{i+1}$$$ explains this case. Similarly, the third term $$$(1-p_i)\cdot e_1$$$ represents the case where the $$$i$$$-th mirror answers NO.
To find $$$e_1$$$ we need to solve $$$n$$$ equations:
(1) $$$e_1 = 1 + p_1 \cdot e_2 + (1-p_1)\cdot e_1$$$
(2) $$$e_2 = 1 + p_2 \cdot e_3 + (1-p_2)\cdot e_1$$$
$$$\ldots$$$
($$$n$$$) $$$e_n = 1 + p_n \cdot e_{n+1} + (1-p_n)\cdot e_1$$$
We can solve this system of equations by using substitution - a common technique. From equation (1) we have $$$e_2 = e_1 - \frac{1}{p_1}$$$. Substituting this in (2) we obtained $$$e_3=e_1-\frac{1}{p_1 \cdot p_2} - \frac{1}{p_2}$$$. See the pattern now? Similarly by substituting to that last equation we have:
$$$0 = e_{n+1}=e_1 - \frac{1}{p_1\cdot p_2 \cdot \ldots \cdot p_n} - \frac{1}{p_2\cdot p_3 \cdot \ldots \cdot p_n} - \ldots - \frac{1}{p_n}$$$
$$$e_1 = \frac{1}{p_1\cdot p_2 \cdot \ldots \cdot p_n} + \frac{1}{p_2\cdot p_3 \cdot \ldots \cdot p_n} + \ldots + \frac{1}{p_n}$$$
$$$e_1 = \frac{1 + p_1 + p_1 \cdot p_2 + \ldots + p_1\cdot p_2 \cdot \ldots \cdot p_{n-1}}{p_1\cdot p_2 \cdot \ldots \cdot p_n}$$$
We can compute $$$e_1$$$ according to the above formula in $$$\mathcal{O}(n)$$$.