[CF1265E] Beautiful Mirrors 期望DP題解

題意簡述

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

1
50

輸出1

2

輸入2

3
10 20 50

輸出2

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∑∞?pi?100?(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}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =pi?100?×j=1∑∞?(1?100pi??)j?1
= ( 100 p i ) 2 =({100 \over p_i})^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(pi?100?)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)×pi?100?
這里需要除法取模，要用到乘法逆元，我用的是費馬小定理，

代碼

#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;
}