Codeforces 1265E Beautiful Mirrors（概率DP，逆元）

思路：

1.记dp[i]为通过第i面镜子的期望天数，pi为通过第i面镜子的概率，则我们可以得到dp[i]=dp[i-1]+pi*1+(1-pi)*(dp[i]+1)，其中的dp[i-1]为走到第i-1的期望天数，此时我们有pi概率只需要再走一天，有1-pi概率需要再走1+dp[i]天（往前走一天，失败，然后再走通过i的期望天数)；
2.除法取模需要用到逆元；

代码：

#include<bits/stdc++.h>
using namespace std;
#define pt(a) cerr<<a<<"---
"
typedef long long LL;
void extgcd(LL a,LL b,LL& x,LL& y){
    if(b==0){x=1,y=0;return;}
    extgcd(b,a%b,x,y);
    LL t=x;x=y;y=t-(a/b)*y;
}
LL mod_inv(LL a,LL m){LL x,y;extgcd(a,m,x,y);return (m+x%m)%m;}
const int maxn=2e5+99;
const LL M=998244353;
int n,p[maxn];
LL dp[maxn],inv[105];
void solve(){
    for(int i=1;i<=n;i++){
        if(inv[p[i]]==0)inv[p[i]]=mod_inv(p[i],M);
        dp[i]=(dp[i-1]+1)*100ll%M*inv[p[i]]%M;
    }
    cout<<dp[n];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i];
	solve();
	return 0;
}