自动搬运

查看原文

来自洛谷，原作者为

	Sooke 做被自己雪藏的耳廓狐 | https://codeforces.com/profile/Sulfox

搬运于2025-08-24 22:02:49，当前版本为作者最后更新于2019-01-18 21:19:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

的确是一道神仙题……网上都找不到一篇详细的题解，可能是我理解能力太差了吧，硬是瞪了好久才看懂。

为了不让大家思维受阻，这里尽我所能地解释清楚。

---

解题思路

首先，您需要认识下面这个式子：

$$\max_k(S) = \sum\limits_{T \subseteq S} (-1)^{|T| - k}\ C_{|T|-1}^{k-1}\min(T) $$

它是 扩展 $\bold{min-max}$ 容斥 的根本。其中 $max_k(S)$ 表示集合 $S$ 中的第 $k$ 大元素，$min(T)$ 表示集合 $T$ 中的最小元素，尽管式子看起来及其玄学，但它确实是可以通过构造两个函数然后二项式反演证明的，想了解具体证明过程的读者可以上网自行学习。

有趣的是，上式可以推广到期望，即：

$$E(\max_k(S)) = \sum\limits_{T \subseteq S} (-1)^{|T| - k}\ C_{|T|-1}^{k-1}E(\min(T)) $$

但在这题中，所谓的 $E(\max_k(S))$ 和 $E(\min(T))$ 都是什么玩意儿？连集合都没有，而且哪来的相对大小？

我们可以假象每一种原料都有一个出现的时间，因为它们出现的时间互不相同，所以可以构成一个集合，所谓 $E(\min(T))$ 显然就是 $T$ 包含的原料最早出现的期望时间，$E(\max_k(S))$ 同理。至于相对大小，因为我们求的本来就是期望，相对对我们来说不重要，只要严格遵循上式计算即可。

为什么要用到这个式子呢？原因是直接算 $E(\max_k(S))$ 太难了，而 $E(\min(T))$ ，我们把 $T$ 中、$T$ 外的原料分别看成整体，每次刷到 $T$ 中原料的概率是 $\frac{\sum\limits_{t \in T}p_t}{m}$ ，期望时间自然就是 $\frac{m}{\sum\limits_{t \in T}p_t}$ 。

另外还有一点，题目里给出的 $k$，实际上代表 $E(\min_{k}(S))$，以下令 $k = n + 1 - k$，以简化得到纯正的 $E(\max_{k}(S))$ 。

好了，该扯的都扯完了，下面我们进入本题最核心的环节——设计 $\bold{dp}$ 。

考虑到 $m$ 和转化后的 $k$ 特别小，很快就能~~（猜）~~想出分别给它们一维。完整地，$f_{k,\,i,\,j}$ 表示确定式子中 $k$ 的值，当前是第 $i$ 种原料，$\sum\limits_{t\in T} p_t = j$ 时的 $\sum\limits_{T \subseteq S} (-1)^{|T| - k}\ C_{|T|-1}^{k-1}$ 的值。

状态很复杂对吧，其实本质上就是把 $k$ 和 $E(\min(T))$ 表示到状态里，给剩下的东西求和，最后再统计状态的贡献。

接下来是转移，很像背包，对于第 $i$ 种原料，如果不选，$f_{k,\,i,\,j} = f_{k,\,i-1,\,j}$，因为没有影响，如果选呢？就有点复杂了。

对于 $i,\,j$ 这两维，必定分别由 $i - 1,\,j - p_i$ 转移而来，但现在主要问题是，如果直接转移，转移后的所有 $|T|$ 都比转移前大 $1$（塞了个 $p_i$ 进去），怎么处理其影响？

幸运的是，$|T|$ 大 $1$，式子里的 $(-1)^{|T|-k}$ 仅仅改了个正负性，而仔细观察 $C_{|T|-1}^{k-1}$，如果 $|T|$ 大 $1$，它可以拆成 $C_{|T|-1}^{k-1} + C_{|T|-1}^{k-2}$（组合数的递推式）！

这就好办多了，拆成两个状态，$C_{|T|-1}^{k-1}$ 的 $k$ 不变，由于 $|T|$ 变了 $1$，所以 $f_{k,\,i-1,\,j-p_i}$ 对 $f_{k,\,i,\,j}$ 有 $-f_{k,\,i-1,\,j-p_i}$ 的贡献。$C_{|T|-1}^{k-2}$ 的 $k$ 小 $1$，$|T|$ 也变了 $1$，负负得正， $f_{k-1,\,i-1,\,j-p_i}$ 对 $f_{k-1,\,i,\,j}$ 有 $f_{k-1,\,i-1,\,j-p_i}$ 的贡献。综上所述，如果选，$f_{k,\,i,\,j} = f_{k-1,\,i-1,\,j-p_i} - f_{k,\,i-1,\,j-p_i}$。真是神仙！

$\mathrm{dp}$ 状态、转移、边界三步走，此时还剩最后一个难关，边界！

如何初始化 $f_{k,\,0,\,0}$ ，使得整个 $\mathrm{dp}$ 滴水不漏呢？全部设 $0$ 显然是不行的，毕竟加加减减也弄不出其他数来，这里有个巧妙的方法，令 $f_{0,\,0,\,0} = 0$，其他 $f_{k,\,0,\,0}=-1$。奇怪的设定，看起来违背状态的定义，实际上是从其他状态反推而来的唯一设定，其可以保证 $|T| = k$ 时的贡献恰好等于 $1\ (0 - (-1) = 1)$，$|T| < k$ 时的贡献恰好等于 $0\ ((-1) - (-1) = 0)$，详见转移式，大家不妨自己去推推看。

最后，枚举 $f_{k,\,n,\,j}$ 中的 $j$，用逆元计算取模意义下的 $\frac{m}{j}$，就可以得出该状态的总贡献啦！

---

代码实现

时空复杂度都是 $O(nmk)$，直接开 $f$ 数组是绝对开不下的，由于其转移过程类似背包，可以把 $i$ 这一维压掉。

乍一看代码好短，然而包含的思维量却是遥不可及的。

#include <cstdio>
#include <algorithm>

inline int read() {
    char c = getchar(); int x = 0;
    while (c < '0' || c > '9') { c = getchar(); }
    while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15); c = getchar(); }
    return x;
}

const int maxN = 1005, maxM = 10005, p = 998244353;

inline int add(int x, int y) { x += y; return x >= p ? x - p : x; }
inline int sub(int x, int y) { x -= y; return x < 0 ? x + p : x; }

int n, m, s, w, ans, inv[maxM], f[12][maxM];

int main() {
    n = read(); s = n + 1 - read(); m = read();
    for (int i = (inv[1] = 1) + 1; i <= m; i++) { inv[i] = (long long) inv[p % i] * (p - p / i) % p; }
    for (int i = 1; i <= s; i++) { f[i][0] = -1; }
    for (int i = 1; i <= n; i++) {
        w = read();
        for (int j = m; j >= w; j--) {
            for (int k = s; k; k--) { f[k][j] = add(f[k][j], sub(f[k - 1][j - w], f[k][j - w])); }
        }
    }
    for (int i = 1; i <= m; i++) { ans = (ans + (long long) f[s][i] * inv[i] % p) % p; }
    printf("%lld\n", (long long) ans * m % p);
    return 0;
}