CF1265E 题解

zzr8178541919 · 2020-11-25 20:59:23 · 题解

Solution

非常经典的一道期望DP题。

期望DP的总体套路一定要会，一般是算从i到n的期望或从1到i的期望

考虑设置状态dp[i]为从1→i的期望次数，那么很自然的有：

我们发现pi×100∈[0,100]之间，所以我们可以 预处理100个逆元,可以使常数降低。

#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define reg register
using namespace std;
const int maxn=7e7+5;
const int mod=998244353;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n;
int p[maxn];
long long inv[105];
long long dp[maxn];
int mul(int x,int y,int mod)
{
    long long res=1;
    while(y)
    {
        if(y & 1)
        res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
int main()
{
    n=read();
    inv[0]=inv[1]=1;
    for(reg int i=2;i<=100;++i)
    {
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    }
    for(reg int i=1;i<=n;++i)
    {
        p[i]=read();
    }
    long long pp=100;
    for(reg int i=1;i<=n;++i)
    {
        dp[i]=pp%mod*(dp[i-1]+1)%mod*inv[p[i]]%mod;
    }
    printf("%lld\n",dp[n]);
    return 0;
}
/*

7
1
1 2 1 
1 3 3
2 4 2
2 5 5
2 6 2
3 7 2

*/