P4707 重返现世 题解

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;
}