GM 有 n ( 1 ≤ n ≤ 2 ∗ 1 0 5 ) n(1≤n≤2*10^5) n(1≤n≤2∗105) 面鏡子，他每天問其中一面鏡子「GM 帥不帥」， i i i 號鏡子有 p i % ( 1 ≤ p i ≤ 100 ) p_i\%(1≤pi≤100) pi%(1≤pi≤100) 的概率回答帥。
第一天，GM 會從 1 1 1 號鏡子開始問起。如果某天 GM 問了 i ( i ≠ n ) i(i≠n) i(i=n)號鏡子，並且鏡子回答帥，那麼第二天 GM 會問 i + 1 i+1 i+1 號鏡子。如果某天 GM 問了 n n n 號鏡子，並且鏡子回答帥，那麼 GM 就覺得很滿意，並且以後不會再問鏡子了。如果某天鏡子沒有回答帥，那麼第二天 GM 會重新從 1 1 1 號鏡子開始問。
求到 GM 滿意為止，問鏡子的期望天數。
第一行輸入一個整數 n ( 1 ≤ n ≤ 2 ∗ 1 0 5 ) n(1 \leq n \leq 2 * 10^5) n(1≤n≤2∗105)，表示鏡子的個數。
第二行輸入 n n n 個整數 p 1 , p 2 , . . . , p n ( 1 ≤ p i ≤ 100 ) p_1,p_2,...,p_n(1 \leq p_i \leq 100) p1,p2,...,pn(1≤pi≤100)。
輸出一個整數，為答案模 998244353 998244353 998244353 的結果。
在第一個樣例，只有一個鏡子，並且它有 1 2 1 \over 2 21 的概率告訴GM 她很漂亮。所以，讓 GM 開心到極點的期望天數是 2 2 2 天。
1
50
2
3
10 20 50
112
令
d
p
[
i
]
dp[i]
dp[i] 為到了第
i
i
i 個鏡子，並且 GM 滿意的期望天數。
如果你學過期望，就不難推出
d
p
[
i
]
=
1
×
(
d
p
[
i
−
1
]
+
1
)
×
p
i
100
+
2
×
(
d
p
[
i
−
1
]
+
1
)
×
p
i
100
×
(
1
−
p
i
100
)
+
k
×
(
d
p
[
i
−
1
]
+
1
)
×
p
i
100
×
(
1
−
p
i
100
)
k
−
1
.
.
.
dp[i]= 1\times (dp[i - 1] + 1) \times {p_i \over 100} + 2 \times (dp[i - 1] + 1) \times {p_i \over 100} \times (1 - {p_i \over 100} ) + k \times (dp[i - 1] + 1) \times {p_i \over 100} \times (1 - {p_i \over 100} ) ^ {k - 1}...
dp[i]=1×(dp[i−1]+1)×100pi+2×(dp[i−1]+1)×100pi×(1−100pi)+k×(dp[i−1]+1)×100pi×(1−100pi)k−1...
=
∑
k
×
(
d
p
[
i
−
1
]
+
1
)
×
p
i
100
×
(
1
−
p
i
100
)
k
−
1
(
k
=
1
,
2
,
3...
)
\ \ \ \ \ \ \ \ \ =\sum k \times (dp[i - 1] + 1) \times {p_i \over 100} \times (1 - {p_i \over 100} ) ^ {k - 1}(k=1,2,3...)
=∑k×(dp[i−1]+1)×100pi×(1−100pi)k−1(k=1,2,3...)
=
(
d
p
[
i
−
1
]
+
1
)
×
p
i
100
×
∑
j
=
1
∞
∑
k
=
j
∞
(
1
−
p
i
100
)
k
−
1
\ \ \ \ \ \ \ \ \ =(dp[i - 1] + 1) \times {p_i \over 100} \times \sum \limits_{j = 1} ^{\infty} \sum \limits_{k = j} ^{\infty}(1 - {p_i\over100})^{k - 1}
=(dp[i−1]+1)×100pi×j=1∑∞k=j∑∞(1−100pi)k−1
突然發現，後面那一堆就是等比數列求和。於是那一堆
=
∑
j
=
1
∞
100
p
i
(
1
−
p
i
100
)
j
−
1
=\sum \limits_{j = 1} ^{\infty}{100 \over p_i}(1 - {p_i\over100})^{j - 1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=j=1∑∞pi100(1−100pi)j−1
=
100
p
i
×
∑
j
=
1
∞
(
1
−
p
i
100
)
j
−
1
={100 \over p_i}\times\sum \limits_{j = 1} ^{\infty}(1 - {p_i\over100})^{j - 1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=pi100×j=1∑∞(1−100pi)j−1
=
(
100
p
i
)
2
=({100 \over p_i})^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=(pi100)2
代入原式，於是
d
p
[
i
]
=
(
d
p
[
i
−
1
]
+
1
)
×
100
p
i
dp[i]=(dp[i - 1] + 1) \times {100 \over p_i}\ \ \ \ \ \ \ \ \ \ \
dp[i]=(dp[i−1]+1)×pi100
這裡需要除法取模，要用到乘法逆元，我用的是費馬小定理。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#define LL long long
using namespace std;
const int MAXN = 2 * 1e5 + 5, Mod = 998244353;
int n, a[MAXN], dp[MAXN];
int Quick_Pow(int x, int y) {
int i = x, j = y, ans = 1;
for(; j; j >>= 1) {
if(j & 1) ans = (LL)ans * i % Mod;
i = (LL)i * i % Mod;
}
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i ++) {
dp[i] = (LL)(dp[i - 1] + 1) * 100 % Mod;
dp[i] = (LL)dp[i] * Quick_Pow(a[i], Mod - 2) % Mod;
}
printf("%d", dp[n]);
return 0;
}