Description
Solution
对于每种原料，如果我们能求出它们的期望出现时间，那么第(k)小的期望出现时间就是答案。因为在第(k)小的原料被收集之前，比它更早出现的原料已经被收集过了，第(k)小的原料就是第(k)个被收集到的原料。
第(k)小的原料其实就是第(n-k+1)大的原料，由于第(k)小和第(k)大都不好求，考虑(min-max)容斥。
考虑(min(T))的求法，因为只要有一个原料收集到就行，所以收集到任何一个元素的概率是(frac{ sum_{ i in T } p_i }{ m })。因为只有两种情况，一种是出现可以收集的原料，一种是不出现，所以这是一个伯努利试验。而伯努利试验的成功期望是成功的概率的倒数，所以(min(T))就是(frac{ m }{ sum_{ i in T } p_i })。
接下来考虑计算答案，因为这道题的(n)比较大，所以不能直接暴力枚举子集(T)，但经过观察，我们发现(m)的范围很小，所以我们计算出每个(min(T))前面的系数，最后枚举所有的(min(T))乘上系数。
设(dp_{i,j,k})表示前(i)个原料，求第(k)大的原料期望出现时间，所有的出现任意一个原料的概率等于(j)的集合前面的系数之和。
考虑转移，如果当前第(i)个原料不在集合(T)中，那么假设我们把它丢掉，不会造成什么影响，(T)的原料个数也不会变，出现任意一个原料的概率也不会改变，所以要加上(dp_{i-1,j,k})。
如果第(i)个原料在集合(T)中，这个时候我们把它丢掉，发现对集合(T)造成了影响，集合(T)中少了第(i)个原料，出现任意一个元素的概率发生了变化，得减去(p_i)。那么(dp)状态中的第三个下标(k)会不会发生变化呢？(肯定的，不然设它干啥)。
当前集合(T)的系数如下
根据组合数的性质，上面的式子等于
观察前(i-1)个原料构成的大小为(left|T ight|-1)的集合中选第(k)大的系数，可以得到
观察前(i-1)个原料构成的大小为(left|T ight|-1)的集合中选第(k-1)大的系数，可以得到
所以当第(i)个原料在集合(T)中时，(dp_{i,j,k})要加上(dp_{i-1,j-p_i,k-1})，减去(dp_{i-1,j-p_i,k})。
初始状态(dp_{i,0,0}=1)，即集合是空集，且求第(0)大，将(k=0)和(left|T ight|=0)代入得出(dp_{i,0,0}=1)。
然而三个维度的(dp)转移空间会爆炸，所以把第一维滚掉，算完系数之后枚举(min(T))乘上系数就行。
Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
const int MOD=998244353;
int n,k,m,p[1050];
ll dp[10050][15],ans;
ll ksm(ll a,ll b)
{
ll tmp=1;
while(b)
{
if(b&1)tmp=(1LL*tmp*a)%MOD;
a=(1LL*a*a)%MOD;
b>>=1;
}
return tmp;
}
int main()
{
scanf("%d%d%d",&n,&k,&m);k=n-k+1;
dp[0][0]=1;
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=p[i];j--)
for(int u=1;u<=k;u++)
dp[j][u]=(dp[j][u]+dp[j-p[i]][u-1]-dp[j-p[i]][u]+MOD)%MOD;
for(int i=1;i<=m;i++)ans=(ans+1LL*dp[i][k]*ksm(i,MOD-2)%MOD*m%MOD)%MOD;
printf("%lld",(ans+MOD)%MOD);
return 0;
}