Mighty Rock Tower
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2400
Tags: brute force, combinatorics, dp, math, probabilities

Pak Chanek comes up with an idea in the midst of boredom to play a game. The game is a rock tower game. There is a big rock that is used as a base. There are also $$$N$$$ small identical rocks that Pak Chanek will use to build a rock tower with a height of $$$N$$$ above the base rock.

Initially, there are no small rocks that are located above the base rock. In other words, the height of the tower above the base rock is initially $$$0$$$. In one move, Pak Chanek can place one small rock onto the top of the tower which makes the height of the tower above the base rock increase by $$$1$$$. Each time Pak Chanek place one small rock, the following will happen after the small rock is placed:

- Let's say $$$x$$$ is the height of the tower above the base rock right after the small rock is placed.
- There is a probability of $$$P_x$$$ percent that the topmost rock falls.
- If $$$x \geq 2$$$ and the topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$2$$$-nd topmost rock also falls.
- If $$$x \geq 3$$$ and the $$$2$$$-nd topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$3$$$-rd topmost rock also falls.
- If $$$x \geq 4$$$ and the $$$3$$$-rd topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$4$$$-th topmost rock also falls.
- And so on.

If the tower successfully reaches a height of $$$N$$$ without any rocks falling after that, then the game is ended.

If given an integer array $$$[P_1, P_2, \ldots, P_N]$$$, what is the expected value of the number of moves that Pak Chanek needs to do to end the game? It can be proven that the expected value can be represented as an simple fraction $$$\frac{P}{Q}$$$ where $$$Q$$$ is coprime to $$$998\,244\,353$$$. Output the value of $$$P \times Q^{-1}$$$ modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — the required height of the rock tower.

The second line contains $$$N$$$ integers $$$P_1, P_2, P_3, \ldots, P_N$$$ ($$$0 \leq P_i \leq 99$$$).

Output format:
An integer representing the expected value of the number of moves that Pak Chanek needs to do to end the game, modulo $$$998\,244\,353$$$.

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

Note:
In the first example, the expected value of the number of moves that Pak Chanek needs to do to end the game is $$$\frac{19}{2}$$$.

Example input:
2
80 50

Example output:
499122186

Example input:
3
25 16 20

Example output:
879786027

Editorial:
Let $$$f(x)$$$ be the the expected number of moves to turn a tower of height $$$x-1$$$ into $$$x$$$. In order to calculate that, let's say the tower's current height is $$$x-1$$$ and we want to make it into $$$x$$$. If we place one small rock, then the following cases can happen:
• With a probability of $$$(P_x\%)^k(1-P_x\%)$$$, exactly $$$k$$$ rocks fall for some $$$0\leq k\leq x-1$$$.
• With a probability of $$$(P_x\%)^x$$$, exactly $$$x$$$ rocks fall.
After moving once, if exactly $$$k$$$ rocks fall for some $$$1\leq k\leq x$$$, then the expected number of moves to make the height of the tower become $$$x$$$ is $$$f(x)+f(x-1)+f(x-2)+\ldots+f(x-k+1)$$$.
From the knowledge above, we get the following formula:
• $$$f(x)=1+(P_x\%)^x(f(x)+f(x-1)+\ldots+f(1))$$$$$$+\sum_{k=1}^{x-1}(P_x\%)^k(1-P_x\%)(f(x)+f(x-1)+\ldots+f(x-k+1))$$$
If we split each term of $$$f$$$ and count the contribution for each of them in the sum, then we will get the following:
• $$$f(x)=1+\sum_{k=1}^x(P_x\%)^kf(x-k+1)$$$
• $$$f(x)=1+(P_x\%)f(x)+\sum_{k=2}^x(P_x\%)^kf(x-k+1)$$$
• $$$(1-P_x\%)f(x)=1+\sum_{k=2}^x(P_x\%)^kf(x-k+1)$$$
• $$$f(x)=\frac{1+\sum_{k=2}^x(P_x\%)^kf(x-k+1)}{1-P_x\%}$$$
Now, we must know how to calculate $$$\sum_{k=2}^x(P_x\%)^kf(x-k+1)$$$ quickly. Notice that there are only $$$100$$$ possible different values of $$$P_x$$$. So we can precompute the values $$$S$$$ with $$$S_{i,j}=\sum_{k=2}^j(i\%)^kf(j-k+1)$$$ for every $$$0\leq i\leq99$$$. We can calculate each value in $$$O(1)$$$ from each previous value if we precompute the values of $$$i\%$$$ for every $$$0\leq i\leq99$$$.
The answer to the original problem is $$$f(1)+f(2)+f(3)+\ldots+f(N)$$$.
Time complexity: $$$O(N\max(P))$$$