310662: CF1866M. Mighty Rock Tower
Description
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$.
InputThe 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$).
OutputAn integer representing the expected value of the number of moves that Pak Chanek needs to do to end the game, modulo $998\,244\,353$.
ExamplesInput2 80 50Output
499122186Input
3 25 16 20Output
879786027Note
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}$.
Output
Pak Chanek在无聊时想出了一个游戏，游戏是建立一个石塔。有一个大石头作为基座，还有N个相同的小石头，Pak Chanek将用这些小石头在大石头上方建立一个高度为N的石塔。最初，没有小石头在大石头上方，也就是说，塔的高度最初是0。每次Pak Chanek可以放置一个小石头在塔顶，使得塔在大石头上方的高度增加1。每当Pak Chanek放置一个小石头后，以下情况会发生：
- 假设x是小石头被放置后塔在大石头上方的高度。
- 有Px%的概率最顶端的石头会掉落。
- 如果x≥2且最顶端的石头掉落了，那么有Px%的概率第二高的石头也会掉落。
- 如果x≥3且第二高的石头掉落了，那么有Px%的概率第三高的石头也会掉落。
- 如果x≥4且第三高的石头掉落了，那么有Px%的概率第四高的石头也会掉落。
- 以此类推。
如果塔在没有石头掉落的情况下成功达到N的高度，那么游戏结束。给定一个整数数组[P1, P2, …, PN]，求Pak Chanek结束游戏所需的期望移动次数。可以证明期望值可以表示为简单分数P/Q，其中Q与998,244,353互质。输出P×Q^(-1)模998,244,353的值。
输入输出数据格式：
输入：
- 第一行包含一个整数N（1≤N≤2×10^5）——石塔所需的高度。
- 第二行包含N个整数P1, P2, P3, …, PN（0≤Pi≤99）。
输出：
- 表示Pak Chanek结束游戏所需的期望移动次数，模998,244,353的整数。题目大意： Pak Chanek在无聊时想出了一个游戏，游戏是建立一个石塔。有一个大石头作为基座，还有N个相同的小石头，Pak Chanek将用这些小石头在大石头上方建立一个高度为N的石塔。最初，没有小石头在大石头上方，也就是说，塔的高度最初是0。每次Pak Chanek可以放置一个小石头在塔顶，使得塔在大石头上方的高度增加1。每当Pak Chanek放置一个小石头后，以下情况会发生： - 假设x是小石头被放置后塔在大石头上方的高度。 - 有Px%的概率最顶端的石头会掉落。 - 如果x≥2且最顶端的石头掉落了，那么有Px%的概率第二高的石头也会掉落。 - 如果x≥3且第二高的石头掉落了，那么有Px%的概率第三高的石头也会掉落。 - 如果x≥4且第三高的石头掉落了，那么有Px%的概率第四高的石头也会掉落。 - 以此类推。 如果塔在没有石头掉落的情况下成功达到N的高度，那么游戏结束。给定一个整数数组[P1, P2, …, PN]，求Pak Chanek结束游戏所需的期望移动次数。可以证明期望值可以表示为简单分数P/Q，其中Q与998,244,353互质。输出P×Q^(-1)模998,244,353的值。 输入输出数据格式： 输入： - 第一行包含一个整数N（1≤N≤2×10^5）——石塔所需的高度。 - 第二行包含N个整数P1, P2, P3, …, PN（0≤Pi≤99）。 输出： - 表示Pak Chanek结束游戏所需的期望移动次数，模998,244,353的整数。