306880: CF1265E. Beautiful Mirrors

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Beautiful Mirrors

题意翻译

### 题目描述: 小C有$N$个从编号分别为$1$到$N$的镜子。她每天都会问一面镜子:“我漂亮吗?”而对于第$i$面镜子,有$p_i \over100$$(1≤i≤n)$的概率告诉小C很漂亮。 她从第一面镜子开始,一个接一个的问镜子。每一天,对于她问的第$i$个镜子,有两种情况: - 如果第$i$个镜子告诉小C她很漂亮:若此时$i=n$,则小C就会开心到极点,停止对镜子的询问。否则,她第二天就会询问第$i+1$个镜子 - 如果第$i$个镜子并没有告诉小C她很漂亮,她就会很伤心,第二天重新从第$1$个镜子开始询问。 你需要计算小C询问完所有镜子后开心到极点的期望天数。若期望天数可被表示为最简分数$p \over q$,则你需要输出的是$p \cdot q^{-1} (mod$ $998244353)$。 ### 输入格式 第一行输入一个整数$n$ $( 1\le n\le 2\cdot 10^5)$,表示镜子的个数。 第二行输入$n$个整数$p_1, p_2 , \ldots , p_n$ $(1 \leq p_i \leq 100)$。 ### 输出格式 输出一个整数,为答案模$998244353$的结果 ### 说明/提示 在第一个样例,只有一个镜子,并且它有$1 \over 2$的概率告诉小C她很漂亮。所以,让小C开心到极点的期望天数是2天

题目描述

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

输入输出格式

输入格式


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

输出格式


Print the answer modulo $ 998244353 $ in a single line.

输入输出样例

输入样例 #1

1
50

输出样例 #1

2

输入样例 #2

3
10 20 50

输出样例 #2

112

说明

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

Input

题意翻译

### 题目描述: 小C有$N$个从编号分别为$1$到$N$的镜子。她每天都会问一面镜子:“我漂亮吗?”而对于第$i$面镜子,有$p_i \over100$$(1≤i≤n)$的概率告诉小C很漂亮。 她从第一面镜子开始,一个接一个的问镜子。每一天,对于她问的第$i$个镜子,有两种情况: - 如果第$i$个镜子告诉小C她很漂亮:若此时$i=n$,则小C就会开心到极点,停止对镜子的询问。否则,她第二天就会询问第$i+1$个镜子 - 如果第$i$个镜子并没有告诉小C她很漂亮,她就会很伤心,第二天重新从第$1$个镜子开始询问。 你需要计算小C询问完所有镜子后开心到极点的期望天数。若期望天数可被表示为最简分数$p \over q$,则你需要输出的是$p \cdot q^{-1} (mod$ $998244353)$。 ### 输入格式 第一行输入一个整数$n$ $( 1\le n\le 2\cdot 10^5)$,表示镜子的个数。 第二行输入$n$个整数$p_1, p_2 , \ldots , p_n$ $(1 \leq p_i \leq 100)$。 ### 输出格式 输出一个整数,为答案模$998244353$的结果 ### 说明/提示 在第一个样例,只有一个镜子,并且它有$1 \over 2$的概率告诉小C她很漂亮。所以,让小C开心到极点的期望天数是2天

加入题单

上一题 下一题 算法标签: