B
题目链接
简要题解
我们发现，只要确定了每一个数出现了多少次，就可以唯一确定当前的一个合法序列，也就是递增序列。
我们不知道这个合法序列的最终长度，但是这个最终长度肯定大于当前长度。
因此我们可以设\(F[i]\)表示最终长度大于\(i\)的概率，那么很容易知道我们所要求的就是$$Ans=\sum_{i=0}^{\infty} (i+1)^2(F[i]-F[i+1])$$
整理一下，可以得到$$Ans=\sum_{i=0}^{\infty} i^2 F[i]-\sum_{i=0}^{\infty} (i+1)^2 F[i+1]+2\sum_{i=0}^{\infty}
iF[i]+\sum_{i=0}^{\infty} F[i]$$
我们需要对这个东西敏感，因为我们可以构造函数来求得\(\sum_{i=0}^{\infty}
iF[i]\) 和\(\sum_{i=0}^{\infty} F[i]\)之间的关系。
单独的\(F[i]\)很难求，但是\(\sum_{i=0}^{\infty} F[i]\)是可以求出来的。
我们利用生成函数，令\(f(x)=\sum_{i=0}^{\infty} F[i]*x^i\)
考虑\(F[i]\)的意义，我们有\(f(x)=\prod_{i=1}^n\sum_{j=0}^{\infty}P_i^j\)，即枚举第\(i\)个数出现了\(j\)次
等比数列求和得到$$f(x)=\prod_{i=1}^n \frac{1}{1-P_i*x}$$
那么$$f(1)=\sum_{i=0}^{\infty} F[i]=\prod_{i=1}^n \frac{1}{1-P_i}$$
我们现在还需要求\(\sum_{i=0}^{\infty} iF[i]\)，事实上只要对\(f(x)\)求导就求出来了
对\(f(x)\)求\(ln\)可以得到$$ln(f(x))=-\sum_{i=1}^{\infty}ln(1-P_i*x)$$
两边求导得到$$ \frac{f'(x)} {f(x)}=\sum_{i=1}^{\infty} \frac{P_i} {1-P_i*x} $$
\[f'(x)=f(x)\sum_{i=1}^{\infty} \frac{P_i} {1-P_i*x} \]并且\(f'(x)=\sum_{i=0}^{\infty} iF[i]*x^{i-1}\)，我们只需要求\(f'(1)\)即可。
代码如下
#include<bits/stdc++.h>
using namespace std;
const int MAXN=110;
const int Mod=998244353;
int n,Sw,W[MAXN],P[MAXN],G[MAXN];
int F=1,F1;
int Pow(int Down,int Up)
{ int Ret=1,Now=Down;
for(;Up>=1;Up>>=1) Up&1?Ret=1ll*Ret*Now%Mod:0,Now=1ll*Now*Now%Mod;
return Ret;
}
int main()
{ scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&W[i]),Sw=(Sw+W[i])%Mod;
for(int i=1;i<=n;i++) P[i]=1ll*W[i]*Pow(Sw,Mod-2)%Mod;
for(int i=1,D;i<=n;i++)
D=Pow((Mod+1-P[i])%Mod,Mod-2),F=1ll*F*D%Mod,F1=(F1+1ll*P[i]*D)%Mod;
printf("%lld\n",(2ll*F*F1+F)%Mod);
}