A101164.Beautiful Mirrors
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Creatnx 有 n 面镜子,编号从 1 到 n。每天,Creatnx 会问恰好一面镜子:“我美吗?”第 i 面镜子会以概率 100pi 告诉 Creatnx 他很美,其中 1≤i≤n。
Creatnx 会从第 1 面镜子开始依次询问。每天,如果他询问第 i 面镜子,会有两种情况:
- 第 i 面镜子告诉 Creatnx 他很美。如果 i=n,Creatnx 就会停止并感到高兴;否则,他会在第二天继续询问第 i+1 面镜子。
- 否则,Creatnx 会感到沮丧。第二天,他会从第 1 面镜子重新开始询问。
你需要计算 Creatnx 变得高兴所需的期望天数。
答案需要对 998244353 取模。形式化地,设 M=998244353。可以证明,答案可以表示为最简分数 qp,其中 p 和 q 是整数,且 q≡0(modM)。输出满足 0≤x<M 且 x⋅q≡p(modM) 的整数 x。
输入格式
第一行包含一个整数 n(1≤n≤2×105)——镜子的数量。
第二行包含 n 个整数 p1,p2,…,pn(1≤pi≤100)。
输出格式
输出一个整数,表示 Creatnx 变得高兴所需的期望天数,对 998244353 取模。
输入输出样例
输入#1
1 50
输出#1
2
输入#2
3 10 20 50
输出#2
112
说明/提示
在第一个测试样例中,只有一面镜子,它以概率 21 告诉 Creatnx 他很美。所以 Creatnx 变得高兴所需的期望天数是 2。