好题,用幂级数算概率。

大概就是考虑容斥, 要算某个集合的人一定在 \(1\) 之后死掉。

\(S\) 为该集合的 \(\sum w_i\)\(sum\) 为所有 \(w_i\) 的和,则概率应该等于 \[ \sum_{i=0}^{\infty} (1-\frac{S+w_1}{sum})^i \frac{w_1}{sum} \]

然后就只需求,对于每个 \(S\) ,有多少种方案,就是个背包。可以 \(NTT\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<vector>
#include<queue>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300005,P=998244353,_G=3;
typedef vector<int> Vint;
int n,w_1,w[maxn];
int Pow(LL a,int b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=(res*a)%P;
return res;
}
int rev[maxn];
void getrev(int n){
int t=0; while((1<<t)<n) t++;
for(int i=1;i<=n-1;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<t-1);
}
void NTT(int a[],int n,int k){
for(int i=0;i<=n-1;i++) if(rev[i]<i) swap(a[rev[i]],a[i]);
for(int m=2;m<=n;m<<=1){
int wm=Pow(_G,(P-1)/m); if(k==-1) wm=Pow(wm,P-2);
for(int i=0;i<=n-1;i+=m){
LL t0,t1,w=1;
for(int j=0;j<=(m>>1)-1;j++,w=w*wm%P)
t0=a[i+j], t1=w*a[i+j+(m>>1)]%P, a[i+j]=(t0+t1)%P, a[i+j+(m>>1)]=(t0+P-t1)%P;
}
}
if(k==-1){
LL t=Pow(n,P-2);
for(int i=0;i<=n-1;i++) a[i]=t*a[i]%P;
}
}
int A[maxn],B[maxn];
Vint Mul(Vint a,Vint b){
int len=max(a.size(),b.size())<<1;
for(int i=0;i<=len-1;i++) A[i]=B[i]=0;
for(int i=0;i<a.size();i++) A[i]=a[i];
for(int i=0;i<b.size();i++) B[i]=b[i];
getrev(len); NTT(A,len,1); NTT(B,len,1);
for(int i=0;i<=len-1;i++) A[i]=(LL)A[i]*B[i]%P;
NTT(A,len,-1);
Vint c; c.clear(); c.resize(len);
for(int i=0;i<=len-1;i++) c[i]=A[i];
return c;
}
struct my_cmp{
bool operator ()(Vint a,Vint b){
return a.size()>b.size();
}
};
priority_queue<Vint,vector<Vint>,my_cmp> pQ;
int ans;
int main(){
scanf("%d%d",&n,&w_1); n--;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
int len=1; while(len<w[i]+1) len<<=1;
Vint c; c.clear(); c.resize(len);
c[w[i]]=P-1; c[0]=1; pQ.push(c);
}
while(pQ.size()>1){
Vint x=pQ.top(); pQ.pop();
Vint y=pQ.top(); pQ.pop();
pQ.push(Mul(x,y));
}
Vint K=pQ.top();
//for(int i=0;i<K.size();i++) printf("%d ",K[i]); printf("\n");
for(int i=0;i<K.size();i++) ans=(ans+(LL)K[i]*Pow(i+w_1,P-2)%P)%P;
ans=(LL)ans*w_1%P;
printf("%d\n",ans);
return 0;
}