Beautiful Mirrors with queries
Contest: Codeforces Round 604 (Div. 1)
Difficulty rating: 2400
Tags: data structures, 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$$$.

Some mirrors are called checkpoints. Initially, only the $$$1$$$st mirror is a checkpoint. It remains a checkpoint all the time.

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 checkpoint with a maximal number that is less or equal to $$$i$$$.

There are some changes occur over time: some mirrors become new checkpoints and some mirrors are no longer checkpoints. You are given $$$q$$$ queries, each query is represented by an integer $$$u$$$: If the $$$u$$$-th mirror isn't a checkpoint then we set it as a checkpoint. Otherwise, the $$$u$$$-th mirror is no longer a checkpoint.

After each query, you need to calculate the expected number of days until Creatnx becomes happy.

Each of this numbers 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 two integers $$$n$$$, $$$q$$$ ($$$2 \leq n, q \le 2 \cdot 10^5$$$)  — the number of mirrors and queries.

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

Each of $$$q$$$ following lines contains a single integer $$$u$$$ ($$$2 \leq u \leq n$$$) — next query.

Output format:
Print $$$q$$$ numbers – the answers after each query by modulo $$$998244353$$$.

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

Note:
In the first test after the first query, the first and the second mirrors are checkpoints. Creatnx will ask the first mirror until it will say that he is beautiful, after that he will ask the second mirror until it will say that he is beautiful because the second mirror is a checkpoint. After that, he will become happy. Probabilities that the mirrors will say, that he is beautiful are equal to $$$\frac{1}{2}$$$. So, the expected number of days, until one mirror will say, that he is beautiful is equal to $$$2$$$ and the answer will be equal to $$$4 = 2 + 2$$$.

Example input:
2 2
50 50
2
2

Example output:
4
6

Example input:
5 5
10 20 30 40 50
2
3
4
5
3

Example output:
117
665496274
332748143
831870317
499122211

Editorial:
Assuming that currently there are $$$k$$$ checkpoints $$$1 = x_1 < x_2 < \ldots < x_k \leq n$$$, the journey becoming happy of Creatnx can be divided to $$$k$$$ stages where in $$$i$$$-th stage Creatnx "moving" from mirror $$$x_i$$$ to mirror at position $$$x_{i+1} - 1$$$. Denote the $$$i$$$-th stage as $$$(x_i, x_{i+1}-1)$$$. These $$$k$$$ stages are independent so the sum of expected number of days Creatnx spending in each stage will be the answer to this problem.
When a new checkpoint $$$b$$$ appear between 2 old checkpoints $$$a$$$ and $$$c$$$, stage $$$(a, c - 1)$$$ will be removed from the set of stages and 2 new stages will be added, they are $$$(a, b - 1)$$$ and $$$(b, c - 1)$$$. Similarly, when a checkpoint $$$b$$$ between 2 checkpoints $$$a$$$ and $$$c$$$ is no longer a checkpoint, 2 stages $$$(a, b - 1)$$$ and $$$(b, c - 1)$$$ will be removed from the set of stages and new stage $$$(a, c-1)$$$ will be added. These removed/added stages can be fastly retrieved by storing all checkpoints in an ordered data structure such as set in C++. For removed/added stages, we subtract/add its expected number of days from/to the current answer. We see that when a query occurs, the number of stages removed/added is small (just 3 in total). Therefore, if we can calculate the expected number of days for an arbitrary stage fast enough, we can answer any query in a reasonable time.
From the solution of problem Beautiful Mirror, we know that the expected number of days Creatnx spending in stage $$$(u, v)$$$ is:
The denominator $$$B$$$ can be computed by using a prefix product array — a common useful trick. We prepare an array $$$s$$$ where $$$s_i = p_1 \cdot p_2 \cdot \ldots \cdot p_i$$$. After that, $$$B$$$ can be obtained by using 1 division: $$$B = \frac{s_v}{s_{u-1}}$$$.
For numerator $$$A$$$, we also use the same trick. An array $$$t$$$ will be prepare where $$$t_i = p_1 + p_1 \cdot p_2 + \ldots + p_1 \cdot p_2 \ldots \cdot p_i$$$. We have $$$t_{v-1} = t_{u-2} + p_1\cdot p_2 \cdot\ldots\cdot p_{u-1} \cdot A$$$ so $$$A = \frac{t_{v-1} - t_{u-2}}{p_1\cdot p_2 \cdot\ldots\cdot p_{u-1}} = \frac{t_{v-1} - t_{u-2}}{s_{u-1}}$$$.