Description
为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 \(n\) 种原料，只需要集齐任意 \(k\) 种，就可以开始制作。
Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 \(i\) 种原料被生成的概率是 \(\frac{p_i}{m}\)。如果 Yopilla 没有这种原料，那么就可以进行收集。
Yopilla 急于知道，他收集到任意 \(k\) 种原料的期望时间，答案对 \(998244353\) 取模。
\(1 \le n \le 1000\)，\(1 \le k \le n, \lvert n - k \rvert \le 10\)，\(0 \le p_i \le m, \sum p = m, 1 \le m \le 10000\)。
Solution
先让 \(k\leftarrow n-k+1\)，那么原题相当于求 \(E\left(\text{kMax}(T)\right)\)，这玩意可以用 min-max 容斥转化为：
\[\sum_{|S|\geq k}{(-1)^{|S|-k}E\left(\text{Min}(S)\right)\binom{|S|-1}{k-1}} \]容易发现对于一个集合 \(S\)，它的第一次出现的期望就是 \(\dfrac{m}{\sum_{i\in S}{p_i}}\)，然后对这个进行 dp 即可。
设 \(f_{i,j,k}\) 表示考虑到了编号 \(1\sim i\)，选了 \(j\) 个数，目前和为 \(k\) 的方案数，直接进行 dp 是 \(O(n^2m)\) 的，过不了。
考虑优化。
注意到 \(\sum{p_i}\) 这个东西在分母，所以一定是无法优化掉的，于是可以考虑把个数那一维去掉。
设 \(g_{i,j}\) 表示目前考虑了 \(1\sim i\)，和为 \(j\) 的所有方案的 \(\sum{\frac{(-1)^{|S|-k}\binom{|S|-1}{k}}{\sum_{p_i}}}\)。
那么如果 \(i\) 不选，则 \(g_{i,j}\leftarrow g_{i-1,j}\)。
如果 \(i\) 选，会发现哪个组合数不好搞，但是注意到 \(\binom{|S|-1}{k-1}=\binom{|S|-2}{k-1}+\binom{|S|-2}{k-2}\)，且前面的 \(-1\) 是好处理的，所以那个组合数也可以 dp 求出。
但是这里 \(k\) 会变化且很小，所以可以记一维 \(k\)，即 \(g_{i,j,k}=g_{i-1,j,k}+g_{i-1,j-p_i,k-1}-g_{i-1,j-p_i,k}\)。
边界是 \(g_{0,0,0}=1\)。
时间复杂度：\(O\left(nm(n-k)\right)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 1e3 + 5, kMaxM = 1e4 + 5, kMaxK = 15, kMod = 998244353;
int n, k, m;
int p[kMaxN], f[2][kMaxM][kMaxK];
constexpr int qpow(int bs, int64_t idx = kMod - 2) {
int ret = 1;
for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
if (idx & 1)
ret = (int64_t)ret * bs % kMod;
return ret;
}
inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }
void dickdreamer() {
std::cin >> n >> k >> m;
k = n - k + 1;
for (int i = 1; i <= n; ++i) std::cin >> p[i];
int o = 0;
f[o][0][0] = 1;
for (int i = 1; i <= n; ++i) {
if (!p[i]) continue;
o ^= 1;
for (int j = 0; j <= m; ++j)
for (int s = 0; s <= k; ++s)
f[o][j][s] = f[o ^ 1][j][s];
for (int j = p[i]; j <= m; ++j) {
for (int s = 1; s <= k; ++s) {
inc(f[o][j][s], sub(f[o ^ 1][j - p[i]][s - 1], f[o ^ 1][j - p[i]][s]));
}
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
inc(ans, 1ll * f[o][i][k] * m % kMod * qpow(i) % kMod);
}
std::cout << ans << '\n';
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}