Beautiful Mirrors with queries

题意翻译

$Creatnx$有$n(n<=2*10^5)$个镜子，编号从$1$到$n$。每天$Creatnx$会去问镜子“我漂亮吗”，第$i$个镜子有$\frac{p_i}{100}(p_i<=100)$的概率回答他是，否则回答他否。 $Creatnx$会从第$1$个镜子开始逐个提问，其中某些镜子被称作“检查点”，**最开始检查点只有1**，对于每次提问： $1.$被回答是：若$Creatnx$询问的是第$n$个镜子，他将停止询问并变得十分开心，否则他会继续询问下一个镜子 $2.$被回答否：$Creatnx$会十分难受，并停止该天的提问，第二天他会从编号小于等于当前镜子的且最近的检查点开始提问。 （即假设他当前询问的$i$，他会找到一个最大的$x$使得$x<=i$并且$x$是检查点，第二天从$x$开始询问） 题目将会有$q(q<=2*10^5)$次修改，每次修改给出一个$u(2<=u<=n)$，若$u$不是检查点则将它变成检查点，否则将$u$变成非检查点。 求每次修改后$Creatnx$期望提问多少次能变得开心，答案对$998244353$取模

题目描述

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](https://en.wikipedia.org/wiki/Expected_value) 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} $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

2 2
50 50
2
2

输出样例 #1

4
6

输入样例 #2

5 5
10 20 30 40 50
2
3
4
5
3

输出样例 #2

117
665496274
332748143
831870317
499122211

说明

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 $ .

题意翻译

$Creatnx$有$n(n<=2*10^5)$个镜子，编号从$1$到$n$。每天$Creatnx$会去问镜子“我漂亮吗”，第$i$个镜子有$\frac{p_i}{100}(p_i<=100)$的概率回答他是，否则回答他否。 $Creatnx$会从第$1$个镜子开始逐个提问，其中某些镜子被称作“检查点”，**最开始检查点只有1**，对于每次提问： $1.$被回答是：若$Creatnx$询问的是第$n$个镜子，他将停止询问并变得十分开心，否则他会继续询问下一个镜子 $2.$被回答否：$Creatnx$会十分难受，并停止该天的提问，第二天他会从编号小于等于当前镜子的且最近的检查点开始提问。 （即假设他当前询问的$i$，他会找到一个最大的$x$使得$x<=i$并且$x$是检查点，第二天从$x$开始询问） 题目将会有$q(q<=2*10^5)$次修改，每次修改给出一个$u(2<=u<=n)$，若$u$不是检查点则将它变成检查点，否则将$u$变成非检查点。 求每次修改后$Creatnx$期望提问多少次能变得开心，答案对$998244353$取模