题目传送门
https://www.luogu.org/problem/P4707
题解
很容易想到这是一个 MinMax 容斥的题目。
设每一个物品被收集的时间为 \(t_i\)，那么集齐 \(k\) 个物品所需时间就是 \(\{t_i\}\) 中的第 \(n-k+1\) 大的时间。
所以我们不妨把 \(k\) 看成原来的 \(n-k+1\)，这个 \(k \leq 11\)。
然后根据扩展 MinMax 容斥
\]
以及期望的线性性质有
\]
所以我们需要做到的就是求出右边的东西。
因为 \(E(\min(T)) = \frac{m}{\sum\limits_{i\in T} p_i}\)，又因为 \(\sum\limits_{i\in T} p_i \leq m \leq 10000\)，而且有用的只有 \(\sum_{i\in T}p_i\)，所以我们很容易得到一个 \(O(n^2m)\) 的做法。
令 \(dp[i][j][k]\) 表示在前 \(i\) 个数中选出来一个大小为 \(k\) 的集合，这个集合的 \(p_i\) 之和为 \(j\) 的总方案。
转移的时候可以类似于 01 背包来转移。
\]
最后答案就是
\]
然而不管这个做法多么好想，它毕竟是 \(O(n^2m)\) 的，只可以通过 \(70\%\) 的测试数据。
我们发现题目中有一个非常重要的条件我们没有用上：\(k \leq 11\)。
可是容斥的时候，\(|T| \geq k\)，这个 \(k\) 的范围完全没有用武之地啊。
回顾前面的 dp 的过程。如果选了一个 \(\sum\limits_{i\in T} p_i = j\) 的集合 \(T\)，并且 \(i \in T\)，那么它是从一个 \(p\) 之和为 \(j - p_i\) 大小为 \(|T|-1\) 的集合转移而来的。
因为一个 \(\sum\limits_{i\in T} p_i = j\) 的集合 \(T\) 的贡献为 \(\sum\limits_{\sum\limits_{i\in T} p_i = j} (-1)^{|T| - k} \binom{|T|-1}{k-1}\)。
我们试着把组合数阶乘拆开，但是似乎发现不了什么有用的东西。但是别忘了，组合数还有另一种拆法：
\]
不妨令 \(dp[i][j][k]\) 表示前 \(i\) 个数，组成的背包总 \(p\) 值为 \(j\)，在基准 \(k\) 为 \(k\) 的时候的总贡献。
于是上面的式子可以写成
\]
同时还需要加上不选的方案
\]
只需要求这个 \(dp\) 数组就可以了。
时间复杂度 \(O(nkm)\)。空间可能会开不下，可以使用滚动数组。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 1000 + 7;
const int M = 10000 + 7;
const int K = 11 + 7;
const int P = 998244353;
int n, m, k;
int p[N], dp[M][K];
inline int smod(int x) { return x >= P ? x - P : x; }
inline void sadd(int &x, const int &y) { x += y; x >= P ? x -= P : x; }
inline int fpow(int x, int y) {
int ans = 1;
for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;
return ans;
}
inline void work() {
k = n - k + 1;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= p[i]; --j)
for (int k = ::k; k; --k) sadd(dp[j][k], smod(dp[j - p[i]][k - 1] + P - dp[j - p[i]][k]));
}
int ans = 0;
for (int i = 1; i <= m; ++i) sadd(ans, (ll)dp[i][k] * m % P * fpow(i, P - 2) % P);
printf("%d\n", ans);
}
inline void init() {
read(n), read(k), read(m);
for (int i = 1; i <= n; ++i) read(p[i]);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}