<h2>题目</h2>
<h2>题解</h2>
每次小 E 肯定会选择获胜概率最大的那个颜色,我们首先考虑如何算出这个概率。
首先题目里的排列形式是没有意义的,可以通过组合数来变成选取一些数。
首先 如果对于颜色 $c$ ,它总共有 $a_c$ 个,这次小 E 手里这个颜色的数的的数量为 $b_c$,令 $N = \sum a_i$,那么获胜概率应该就是:
$$\frac{\sum_{i} \binom {a_c - b_c}{i} \binom {N-(a_c-b_c)-x}{y-i}[b_c-i \geq z]}{\binom {N - x} y}$$
然后发现不同的概率的数目是 $O(N)$ 的,所以我们首先把所有的概率都求出来,然后我们枚举一个最大值,然后我们算出来所有情况中满足最大值是这个数的情况的概率,乘上获胜概率就是这种情况的获胜概率了。
假设我们已经知道了第 $i$ 个颜色选择了 $b_i$ 个,那么利用简单的组合计数可以得到概率:
$$\frac{\prod_i \binom {a_i}{b_i}}{\binom N x}$$
这个概率是可以用简单的 dp 计算出来的,然后乘起来就好了。
代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define BLL __int128_t
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define P std::pair<BLL,std::pair<int,int> >
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 100+5;
const int ha = 998244353;
int n,x,y,z,a[MAXN],lim[MAXN],N;
int fac[MAXN],inv[MAXN];
std::vector<P> G;
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1llresa%ha;
a = 1llaa%ha;
n >>= 1;
}
return res;
}
inline void prework(){
fac[0] = 1;
FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
inv[MAXN-1] = qpow(fac[MAXN-1]);
ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
}
inline BLL _C(int n,int m){
if(n < m) return 0;
BLL ans = 1;
FOR(i,n-m+1,n) ans = ans*i;
FOR(i,2,m) ans /= i;
return ans;
}
inline int C(int n,int m){
if(n < m) return 0;
return fac[n]inv[m]%hainv[n-m]%ha;
}
inline void prob(int col,int a,int b){
BLL res = 0;
FOR(i,0,std::min(y,b-z)) res += _C(a-b,i)*_C(N-(a-b)-x,y-i);
G.pb(MP(res,MP(col,b)));
}
inline int prob(int a,int b){
int res = 0;
FOR(i,0,std::min(y,b-z)) (res += C(a-b,i)*C(N-(a-b)-x,y-i)%ha)%=ha;
return res;
}
int fMAXN;
inline int calc(int p,int s){
CLR(f,0);f0 = 1;
FOR(i,1,n){
if(i == p) FOR(j,0,s) fi = fi-1;
else{
FOR(j,0,lim[i]) FOR(k,0,std::max(0ll,s-j)){
(fi += fi-1*C(a[i],j)%ha) %= ha;
}
}
}
return fn;
}
signed main(){
prework();
scanf("%lld%lld%lld%lld",&n,&x,&y,&z);
FOR(i,1,n) scanf("%lld",a+i),N += a[i];
FOR(i,1,n){
FOR(j,z,std::min(x,a[i])){ // 第 i 个 颜色用了 j 个的 prob
prob(i,a[i],j);
}
}
std::sort(all(G));
int ans = 0;
FOR(i,1,n) lim[i] = std::min(a[i],z-1);
for(auto x:G)
(ans += calc(x.se.fi,::x-x.se.se)prob(a[x.se.fi],x.se.se)%haC(a[x.se.fi],x.se.se)%ha) %= ha,
lim[x.se.fi] = x.se.se;
printf("%lldn",ansqpow(C(N-x,y)C(N,x)%ha)%ha);
return 0;
}