链接：https://ac.nowcoder.com/acm/contest/11255/B

这篇题解可能会有些许错误，欢迎大佬们指正Orz

概率生成函数

首先，我们定义概率生成函数
(为啥这么定义？菜了，不大清楚，当一个做题方向吧)
我们现在需要的出这个函数。

由题意可知：我们抽到的数字的序列，除去最后一个数之外，它肯定是一个不下降的序列，像是1，1，2，3，3，7这样的。这时，我们可以枚举每个数的出现次数，来得到（指的是数字i被抽到的概率）
具体的，假如1，1，2，3，3，7这样的序列，对应的就是。我们某个数出现的次数的生成函数，则我们可以知道。
根据等比数列求和，
因此，
记住这个函数，我们后面会用到它。
PS.枚举了1，1，3，3，7这种序列后游戏并没有结束，因此它是P(len>i)的概率。

回到题目，我们要求的是的期望，那么，用上面的东西表示其实是：

这里有一些细节可能需要学过生成函数才能比较好理解，这里不再展开。
ps.官方题解这里第一步有些许不同，但是推到结果相同，不知道是我理解有错还是出题人笔误？欢迎大佬们指出。

upd.这里有大佬说推导会漏掉这一项，但目前还没想出问题所在Orz。

upd 2021.7.21. 修改了第4行处一处错误，感谢各位大佬的指正Orz。

注意：以后推累加的式子最好都把前几项写出来看下。
之后就是怎么求这个式子的问题了。
首先是怎么求，这个好解决，。
之后，根据，x=1带入也可以得到f(1)。
而对于，我们这样考虑：
对于形如函数，其导数为
因此，对于，g(x)形如h(x)
其导数为

因此，
这样就求和，后面求和直接计算出来，乘上f（1）即可。

#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cctype>
#define inf 0x3f3f3f3f
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod = 998244353;
namespace FastIO
{
    char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
    int p, p3 = -1;
    void read() {}
    void print() {}
    inline int getc()
    {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline void flush()
    {
        fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
    }
    template <typename T, typename... T2>
    inline void read(T &x, T2 &...oth)
    {
        int f = 0;
        x = 0;
        char ch = getc();
        while (!isdigit(ch))
        {
            if (ch == '-')
                f = 1;
            ch = getc();
        }
        while (isdigit(ch))
        {
            x = x * 10 + ch - 48;
            ch = getc();
        }
        x = f ? -x : x;
        read(oth...);
    }
    template <typename T, typename... T2>
    inline void print(T x, T2... oth)
    {
        if (p3 > 1 << 20)
            flush();
        if (x < 0)
            buf2[++p3] = 45, x = -x;
        do
        {
            a[++p] = x % 10 + 48;
        } while (x /= 10);
        do
        {
            buf2[++p3] = a[p];
        } while (--p);
        print(oth...);
    }
} // namespace FastIO
#define read FastIO::read
#define write FastIO::print
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) { return a / gcd(a, b) * b; };
ll ksm(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}
//==============================================================
const int maxn=105;
#define MOD(x) (((x)%mod+mod)%mod)
ll n,p[maxn];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    //clock_t c1 = clock();
    //===========================================================
    read(n);
    int sum=0;
    rep(i,1,n)read(p[i]),sum=(sum+p[i]);
    for(int i=1;i<=n;++i){
        p[i]=MOD(p[i]*ksm(sum,mod-2));
    }
    ll fval=1;
    for(int i=1;i<=n;++i){
        fval*=ksm(1-p[i],mod-2);
        fval=MOD(fval);
    }
    ll gval=0;
    for(int i=1;i<=n;++i){
        gval+=1ll*p[i]*ksm(1-p[i],mod-2);
        gval=MOD(gval);
    }
    ll f_val=gval*fval;
    cout<<MOD(f_val*2%mod+fval)<<endl;
    //===========================================================
    FastIO::flush();
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}

期望dp

看到有大佬用的期望dp。其实比赛的时候也想过，但是最后十分钟发现题意假了，怕了，没想出来。

其实期望dp的转移是比较套路的，一般难点在状态设计上。但是这题的状态设计其实又比较明显：
对于的期望，我们一般还是先考虑求的期望，再根据期望的线性性解决。
由于这题的步骤可以有无限步，因此不可能选择步数作为状态。显然，我们选择的会是目前的最大值。
dp[i]表示非递减部分现在最大值为i时，还需要生成的数的个数的期望，则：
dp[i]有两个来源：
1、下一步选到了一个数j>=i，则还需要继续选择，这一步的概率为，
2、下一步选到了一个数j<i，则下一步就结束，这一步的概率也为
因此，可以列出dp转移方程：

化简下就是

从n->1推即可。

对于：
由
得：

同理化简得：

同样推即可。
答案为：
或者上面的
因为我们算(i>0)实际是已经选取了一个数后再进行的。

mod=998244353
dp=[i for i in range(105)]
dp2=[i for i in range(105)]
p=[i for i in range(105)]
n=int(input())
w=list(map(int,input().split()))

sum=0
for x in w:
    sum+=x
Inv=pow(sum,mod-2,mod)

for i in range(n):
    p[i]=w[i]*Inv%mod

for i in reversed(range(n)):
    pre=0
    suf=0
    for j in range(i):
        pre+=p[j]
        pre%=mod
    for j in range(i+1,n):
        suf+=p[j]*(dp[j]+1)%mod
        suf%=mod
    inv=pow((1-p[i])%mod,mod-2,mod)
    dp[i]=(pre+suf+p[i])*inv%mod
for i in reversed(range(n)):
    up=0
    for j in range(i+1,n):
        up+=p[j]*(dp2[j]+2*dp[j]+1)%mod
        up%=mod
    for j in range(i):
        up+=p[j]
        up%=mod
    up+=2*p[i]*dp[i]+p[i]
    up%=mod
    down=pow((1-p[i])%mod,mod-2,mod)
    dp2[i]=up*down%mod

print(dp2[0])