Sample Game

题面描述

Bob 有一个随机数生成器，它生成 x 的概率为 p_x

现在 Bob 将做以下操作：

第一步：通过随机数生成器生成一个数字 x

第二步：如果 x 是所生成的所有数中最大的一个（ x 不小于任何之前生成的数），返回第一步。否则前往第三步

第三步：如果 Bob 一共生成了 x 个数字，Bob 将得到 x^2 分

Bob 想知道他得分的期望。

Solution

期望 dp

设 f[i] 表示当前处于非递减部分，且最大值为 i 时，期望生成 f[i] 个数才能结束游戏。（相当于 x ）

g[i] 表示当前处于非递减部分，且最大值为 i 时，期望生成得 g[i] 分才能结束游戏。（相当于 x^2）

先看 f[i] 的转移。

当前最大的数为 i ，设下一步选择的数是 j 。

若 j< i ，则下一步游戏结束，期望再走一步，概率为 p[j]。

若 j\geq i，则要从 f[j] 转移，概率为 p[j]。

则有递推式

f[i]=\sum_{j=1}^{i-1}p_j\times1+\sum_{j=i}^{n} p_j\times(f[j]+1)

两边都含 f[i] 移向得到

f[i]=\frac{\sum_{j=i+1}^nf[j]\times p[j]+1}{1-p_i}
对于期望 E((x+1)^2) 有

E((x+1)^2) = E(x^2+2\times x+1)=E(x^2)+2\times E(x)+1

再考虑 g[i] 的转移

g[i]=\sum_{j=1}^{i-1}p_j\times1+\sum_{j=i}^np_j\times(g[j]+2\times f[i]+1)

移向有

g[i]=\frac{\sum_{j=i+1}^np[j]\times g[j]+\sum_{j=i}^np[j]\times f[j]+1}{1-p_i}

答案即为 g[0] 或是

ans=\sum_{i=1}^np_i\times(g[i]+2 \times f[i]+1)

#include<bits/stdc++.h>
#define ll long long
const int N = 105;
const ll mod = 998244353;
int n;
ll s,p[N],f[N],g[N],inv[N];
ll qpow(ll a,ll b){
    if(b==0) return 1;
    ll w = qpow(a,b/2);
    w=w\timesw%mod;
    if(b&1) w=w\timesa%mod;
    return w;
}
int main(){
    scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%lld",&p[i]),inv[i]=qpow(i,mod-2),s+=p[i];

    s = qpow(s,mod-2);

    for(int i=1;i<=n;++i) p[i]=p[i]\timess%mod ;

    for(int i=n;i;--i){
        ll up = 1,down = (1-p[i]+mod)%mod;
        for(int j=i+1;j<=n;++j) up=(up+f[j]\timesp[j]%mod)%mod;
        f[i] = up\timesqpow(down,mod-2)%mod;
    }
    for(int i=n;i+1;--i){
        ll up = 1,down = (1-p[i]+mod)%mod;
        for(int j=i+1;j<=n;++j)
            up=(up+p[j]\timesg[j]%mod)%mod;
        for(int j=i;j<=n;++j)
            up=(up+2\timesp[j]\timesf[j]%mod)%mod;
        g[i]=up\timesqpow(down,mod-2)%mod;
    }
    printf("%lld",g[0]);
    return 0;
}