题意
有一个随机数生成器，生成数(x)的概率为(p_x)。现在我们进行如下操作直至结束：
(1) 随机生成一个数(x)。
(2) 如果已经生成的数中没有比(x)更大的数，则返回操作(1)，否则，记当前已经生成的数的个数为(z)，则得到(z^2)分，操作结束。
求得分的期望。
(2le nle 100)
题解
容易发现，如果操作没有停止，则已经生成的数一定是类似于(1,1,2,3,4,5,5...)(按生成顺序排列)这样的非递减序列。设(X)为已经生成的数的个数，则(X)是(Bbb{N})上的离散随机变量。记(g_i=P(X>i))，即长度为(i)时还没有停止的概率。下面考虑如何计算(P(X>i))，假设当前长度为(L)，数(x)的出现次数为(cnt_x)，由于这些数的出现次序是固定的，故有
[P(X>L)=sumprod_{sum cnt_x=L}p_x^{cnt_x}
]
则({g_i})对应的生成函数为
[egin{align}
G(x)=sum_{i=0}^{infty}g_ix^i=sum_{i=0}^{infty}P(X>i)x^i=prod_{k=1}^{n}sum_{i=0}^{infty}p_k^ix^i=prod_{k=1}^{n}frac{1}{1-p_kx}
end{align}
]
则得分的期望为
[egin{align}
E&=sum_{i=1}^{infty}P(X=i)i^2\
&=sum_{i=1}^{infty}(P(Xge i)-P(Xge i+1))i^2\
&=sum_{i=0}^{infty}(P(X> i)-P(X> i+1))(i+1)^2\
&=sum_{i=0}^{infty}P(X> i)(i+1)^2-sum_{i=0}^{infty}P(X> i+1)(i+1)^2\
&=sum_{i=0}^{infty}P(X> i)(i+1)^2-sum_{i=1}^{infty}P(X> i)i^2\
&=sum_{i=0}^{infty}P(X> i)(i+1)^2-sum_{i=0}^{infty}P(X> i)i^2\
&=sum_{i=0}^{infty}P(X> i)((i+1)^2-i^2)\
&=sum_{i=0}^{infty}P(X> i)(2i+1)\
&=2G'(1)+G(1).\
end{align}
]
由于
[frac{G'(x)}{G(x)}=[ln G(x)]'=[sum_{k=1}^{n}ln frac{1}{1-p_kx}]'=sum_{k=1}^{n}frac{p_k}{1-p_kx},
]
故
[G'(x)=G(x)sum_{k=1}^{n}frac{p_k}{1-p_kx}.
]
#include <bits/stdc++.h>
using namespace std;
using ll=long long ;
const ll M=998244353;
ll ans=1,a[102];
int n;
ll pm(ll x,ll b){x%=M;ll res=1;while(b){if(b&1)res=res*x%M;x=x*x%M;b>>=1;}return res;}
void f1(){
cin>>n;
ll na=0,ans=1,res=0;
for(int i=1;i<=n;i++){
cin>>a[i];na+=a[i];na%=M;
}
ll inv=pm(na,M-2);
for(int i=1;i<=n;i++){
a[i]=a[i]*inv%M;
ll tmp=pm(1+M-a[i],M-2);
res+=tmp*a[i]%M;
res%=M;
ans=ans*tmp%M;
}
res=(res*2%M+1)%M;
ans=ans*res%M;
cout<<ans;
}
int main(){
f1();
return 0;
}