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;
}
0 条评论