CF1265E题解

PenguinJ · 2025-09-11 20:45:15 · 题解

题目。

设 f_i 表示问完了前 i-1 面镜子，还期望要多少天。

有 f_i=p_i f_{i+1}+(1-p_i)f_1 +1,f_{n+1}=0 ，答案即为 f_1 。

将递推式变形，有 f_i-f_1=p_i(f_{i+1}-f_1)+1。

记 g_i=f_i-f_1，则 g_i=p_i g_{i+1}+1,g_{i+1}=\frac{g_i-1}{p_i},g_1=f_1-f_1=0。

于是我们可以递推求出所有的 g_i 。

因为 f_n=p_n f_{n+1}+(1-p_n)f_1+1=f_1-p_n f_1+1，所以 f_n-f_1=g_n=1-p_n f_1,f_1=\frac{1-g_n}{p_n}。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll n,p[200005],g[200005],ans;
inline ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1; 
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    g[1]=0;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        p[i]=p[i]*qpow(100,mod-2)%mod;
        g[i+1]=(g[i]-1+mod)%mod*qpow(p[i],mod-2)%mod;
    }
    ans=mod-g[n+1];
    cout<<ans;
    return 0;
}