发现直接记录有哪些奖品被选是不可能的，所以考虑转换一下思路：设 \(dp_{i,j,p}\) 为只考虑前 \(i\) 个奖品，抽了 \(j\) 次，有 \(p\) 种不同奖品的的概率。
这个状态相当于是维护一个操作（抽奖）序列。考虑每次加入 \(q\) 个第 \(i\) 种奖品，就相当于是将原序列和一个由 \(q\) 个 \(i\) 组成的序列合并。这是经典问题，方案数即为 \(\dbinom{j}{q}\)。而该序列出现概率又为 \(dp_{i-1,j-q,p-1}\times (\dfrac{w_i}{\sum w})^q\)。还需要判断一下一些 \(0/1\) 的情况。
code：
点击查看代码
int n,m,k,e[N],f[N],dp[N][N][N];
inline int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)
ret=1ll*ret*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return ret;
}
inline int Cnm(int x,int y){
if(x<0||y<0||x<y)
return 0;
return 1ll*f[x]*qpow(1ll*f[y]*f[x-y]%mod,mod-2)%mod;
}
void solve(){
scanf("%d%d%d",&n,&m,&k);
int sm=0;
f[0]=1;
for(int i=1;i<=k;i++)
f[i]=1ll*f[i-1]*i%mod;
for(int i=1;i<=n;i++){
scanf("%d",&e[i]);
sm+=e[i];
}
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
dp[i][0][0]=dp[i-1][0][0];
for(int j=1;j<=k;j++){
for(int p=1;p<=min(i,m);p++){
dp[i][j][p]=dp[i-1][j][p];
for(int q=1;q<=j;q++){
dp[i][j][p]=(dp[i][j][p]+1ll*dp[i-1][j-q][p-1]*Cnm(j,q)%mod*qpow(e[i],q)%mod*qpow(qpow(sm,q),mod-2)%mod)%mod;
}
}
}
}
printf("%d\n",dp[n][k][m]);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
solve();
}