理解了好久$min-max$容斥
Description
Solution
对于每种原料，如果我们能求出它们的期望出现时间，那么第$k$小的期望出现时间就是答案。因为在第$k$小的原料被收集之前，比它更早出现的原料已经被收集过了，第$k$小的原料就是第$k$个被收集到的原料。
第$k$小的原料其实就是第$n-k+1$大的原料，由于第$k$小和第$k$大都不好求，考虑$min-max$容斥。
$$kthmax(S)=\sum_{T\subseteq S}(-1)^{\left|T\right|-x}\times\binom{\left|T\right|-1}{x-1}min(T)$$
考虑$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$的系数如下
$$\binom{\left|T\right|-1}{k-1}(-1)^{\left|T\right|-k}$$
根据组合数的性质，上面的式子等于
$$\left[ \binom{\left|T\right|-2}{k-1} + \binom{\left|T\right|-2}{k-2}\right] (-1)^{\left|T\right|-k}$$
$$=\binom{\left|T\right|-2}{k-1}(-1)^{\left|T\right|-k} + \binom{\left|T\right|-2}{k-2}(-1)^{\left|T\right|-k}$$
观察前$i-1$个原料构成的大小为$\left|T\right|-1$的集合中选第$k$大的系数，可以得到
$$\binom{\left|T\right|-2}{k-1}(-1)^{\left|T\right|-k-1}=-\binom{\left|T\right|-2}{k-1}(-1)^{\left|T\right|-k}$$
观察前$i-1$个原料构成的大小为$\left|T\right|-1$的集合中选第$k-1$大的系数，可以得到
$$\binom{\left|T\right|-2}{k-2}(-1)^{\left|T\right|-k-1+1}=\binom{\left|T\right|-2}{k-2}(-1)^{\left|T\right|-k}$$
所以当第$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\right|=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;
}