Beautiful Mirrors (Codeforces 1265E)
Tags: Math, 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$$$.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 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}$$$.

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

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

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

Sample Inputs:
1
50

3
10 20 50

Sample Outputs:
2

112

Solution (Python):
import time
import sys
f = sys.stdin
t1 = time.time()
n = int(f.readline())
MOD = 998244353
prob = list(map(int, f.readline().split()))
num = pow(100, n, MOD)
new_term = num
inv_100 = pow(100, MOD - 2, MOD)
for x in prob[:-1]:
    new_term = new_term * x * inv_100 % MOD
    num = (num + new_term) % MOD
t4 = time.time()
den = new_term * prob[-1] * inv_100
inverse = pow(den, MOD - 2, MOD)
print(num * inverse % MOD)

Solution (Python):
M = 998244353

def gcd(a, b):
    if a == 0:
        return (0, 1)
    (x, y) = gcd(b % a, a)
    return (y - b // a * x, x)
k = input()
probs = list(map(int, input().split(' ')))
(num, denum) = (0, 1)
for p in probs:
    num = (num + denum) * 100 % M
    denum = denum * p % M
(inv, _) = gcd(denum, M)
print(num * inv % M)

Solution (Python):
M = 998244353
n = input()
p = list(map(int, input().split(' ')))
num = 0
denum = 1
for i in p:
    num = (num + denum) * 100 % M
    denum = denum * i % M
from math import gcd
g = gcd(num, denum)
num = num // g
denum = denum // g
denum = pow(denum, M - 2, M)
print(num * denum % M)