隔壁友校的初一已经开始做这种题了，准老年选手感到恐惧。
思路
Min-Max 容斥。
首先考虑到 \(|n - k| \leq 10\)，感觉有大力做法，考虑用 Min-Max 容斥求期望。
设全集 \(U\) 为每种原料的出现时间构成的集合，现在需要求的是 \(E(\operatorname{kthmin}(U))\).
注意到第 \(k\) 小等价于第 \(n - k + 1\) 大，所以可以转化成求 \(E(\operatorname{kthmax}(U))\).
根据 Min-Max 容斥可以转化成求 \(\sum\limits_{T \subseteq U} (-1)^{|T| - k} {|T - 1| \choose k - 1} E(\min(T))\).
\(E(\min(T))\) 可以 \(O(1)\) 求。考虑某个时刻选中 \(T\) 中元素的概率为 \(\sum\limits_{v \in T} \frac{p_v}{m}\)，那么根据期望定义得：
\(E(\min(T)) = \sum\limits_{k = 1}^{\infty} (1 - \sum\limits_{v \in T} \frac{p_v}{m})^{k - 1} \sum\limits_{v \in T} \frac{p_v}{m} k\).
无穷级数求和得 \(E(\min(T)) = \frac{m}{\sum\limits_{v \in T} p_v}\).
为方便起见，令 \(p_i \leftarrow p_i \cdot m\).
现在的问题是朴素枚举子集的复杂度是假的，需要优化。
不妨考虑用 dp 快速统计贡献系数。观察到 \(E(\min(T))\) 主要和 \(\sum\limits_{v \in T} p_v\) 有关，考虑设进状态。
令 \(f[i][j][k]\) 表示前 \(i\) 个元素中选了 \(j\) 个，并且选中元素的概率之和为 \(k\) 的方案总数，转移直接分讨当前元素是否选择就行。时间复杂度 \(O(n^2 m)\).
观察贡献，注意到 dp 求方案数最终还需要乘上 Min-Max 容斥赋予的系数，所以才需要加一维记录 \(|T|\)。可以考虑把这个系数加入状态来降维。
直觉上设 \(f[i][j]\) 表示前 \(i\) 个元素，概率之和为 \(j\) 时 \(\sum\limits_{T \subseteq U} (-1)^{|T| - k} {|T - 1| \choose k - 1}\) 的值，但是注意到 \(k\) 不是定值，所以很难转移。
考虑把此时的贡献写出来：
\(\sum\limits_{T \subseteq U} (-1)^{|T| + 1 - k} {|T| \choose k - 1}\).
根据组合数的递推式把它拆开：
\(\sum\limits_{T \subseteq U} (-1)^{|T| + 1 - k} {|T| \choose k - 1} = \sum\limits_{T \subseteq U} (-1)^{|T| + 1 - k} [{|T| \choose k - 2} + {|T - 1| \choose k - 1}]\)
进一步拆开得到：
\(\sum\limits_{T \subseteq U} (-1)^{|T| + 1 - k} {|T| \choose k - 2} - \sum\limits_{T \subseteq U} (-1)^{|T| - k} {|T - 1| \choose k - 1}\).
前面实际上是求 \(k^{\prime} = k - 1\) 时的答案，后面实际上是 \(f[i - 1][j]\).
所以现在只需要在状态中钦定 \(k\) 就可以直接转移了。因为有 \(|n - k| \leq 10\)，所以此处 \(k \leq 11\)，直接加进状态复杂度也是对的。
所以考虑设 \(f[i][j][k]\) 表示前 \(i\) 个元素，概率之和为 \(j\)，求的是 \(\operatorname{kthmax}\) 时 \(\sum\limits_{T \subseteq U} (-1)^{|T| - k} {|T - 1| \choose k - 1}\) 的值。
转移是 \(f[i][j][k] = f[i - 1][j][k - 1] - f[i - 1][j][k]\).
边界是 \(f[0][0][0] = 1\).
三维数组开不下，考虑把第一维滚掉。
时间复杂度 \(O(n m |n - k|)\)
代码
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const int maxm = 1e4 + 5;
const int maxd = 11;
const int mod = 998244353;
int n, m, k;
int p[maxn];
ll f[maxd][maxm];
ll qpow(ll base, ll power)
{
ll res = 1;
while (power)
{
if (power & 1) res = 1ll * res * base % mod;
base = 1ll * base * base % mod;
power >>= 1;
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &k, &m), k = n - k + 1;
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
f[0][0] = 1;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (!p[i]) continue;
for (int j = m - p[i]; j >= 0; j--)
for (int l = k; l; l--)
{
f[l][j + p[i]] = (f[l][j + p[i]] + f[l - 1][j] - f[l][j]) % mod;
f[l][j + p[i]] = (f[l][j + p[i]] + mod) % mod;
}
}
for (int i = 1; i <= m; i++) ans = (ans + f[k][i] * m % mod * qpow(i, mod - 2) % mod) % mod;
printf("%d\n", (ans + mod) % mod);
return 0;
}