1866M - Mighty Rock Tower - CodeForces Solution

#include <bits/stdc++.h>
//#include <bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;typedef unsigned long long ull;
typedef pair<int, int> pii;typedef pair<ll, ll> pll;
const int MAXN=2e5+5,INF=0x3f3f3f3f,MOD=998244353;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
//const double PI=acos(-1);

int add(int a,int b) {return (a+b)%MOD;}
int sub(int a,int b) {return (a+MOD-b)%MOD;}
int mul(int a,int b) {return 1ll*a*b%MOD;}
int mpow(int a,ll p)
{
    if(p==0) return 1;
    else if(p%2) return 1ll*a*mpow(a,p-1)%MOD;
    else return mpow(1ll*a*a%MOD,p/2);
}
int dv(int a,int b) {return 1ll*a*mpow(b,MOD-2)%MOD;}

pii S[MAXN][100],E[MAXN];
int p[MAXN],P[100];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i=0; i<100; ++i)
    {
        P[i]=dv(i,100);
    }
    
    int n;cin>>n;
    for (int i=1; i<=n; ++i)
    {
        cin>>p[i];
    }

    E[0]={1,0};
    for (int i=1; i<=n; ++i)
    {
        E[i].first=sub(dv(sub(E[i-1].first,mpow(P[p[i]],i)),sub(1,P[p[i]])),S[i-1][p[i]].first);
        E[i].second=sub(dv(sub(E[i-1].second,1),sub(1,P[p[i]])),S[i-1][p[i]].second);
        for (int j=0; j<100; ++j)
        {
            S[i][j].first=mul(P[j],add(S[i-1][j].first,E[i].first));
            S[i][j].second=mul(P[j],add(S[i-1][j].second,E[i].second));
        }
    }
    
    cout<<dv(sub(0,E[n].second),E[n].first)<<'\n';

    return 0;
}