文章目录

洛谷 P4707 重返现世 做题笔记

发布于

题意

有 $n$ 种物质，每单位时间会随机生成一种物质，生成第 $i$ 种物质的概率为 $\frac{p_i}m$。求获得 $k$ 种物质的期望时间。

$1 \leq n \leq 1000, 1 \leq m \leq 10000, 1 \leq k \leq n, n - k \leq 10$

题解

考虑直接使用 Min - kMax 容斥 公式。
$$E\left(\operatorname{kmax}\left(S\right)\right) = \sum\limits_{T \subseteq S, \left\lvert T \right\rvert \geq k} \left(-1\right)^{\left\lvert T \right\rvert - k} \binom{\left\lvert T \right\rvert - 1}{k - 1}E\left(\min\left(T\right)\right)$$

因为，物质正好生成到集合 $S$ 中的概率就是 $\displaystyle \frac{\sum\limits_{i \in S} p_i}m$，而期望次数就是它的倒数。此时，$\displaystyle E\left(\min\left(S\right)\right) = \frac m{\sum\limits_{i \in S} p_i}$。

这样时间复杂度是 $\Theta \left(2^n\right)$ 的。实际上，$\min\left(S\right)$ 只和 $\sum\limits_{i \in S} p_i$ 有关。因此，状态数其实只有 $m$ 种，可以使用动态规划快速求解。

我们可以设 $f_{i, j, l}$ 表示前 $i$ 种物质选出 $j$ 个且 $\sum\limits_{i \in S} p_i = l$ 的方案数。
复杂度 $\Theta \left(n^2 m\right)$。

但是注意到，$n - k \leq 10$，所以可以改一下状态：
$f_{i, j, k}$ 表示前 $i$ 个物质中，$\sum\limits_{i \in S} p_i = j$ 时 $\displaystyle \left(-1\right)^{\left\lvert T \right\rvert - k} \binom{\left\lvert T \right\rvert - 1}{k - 1}$ 的和。

考虑转移：

  • 如果第 $i$ 个物质不选，那么 $f_{i, j, k} = f_{i - 1, j, k}$。
  • 如果选第 $i$ 个物质的话，我们可以使用组合数递推公式递推。
    $$\left(-1\right)^{\left\lvert T \right\rvert - k} \binom{\left\lvert T \right\rvert - 1}{k - 1} = - \left(-1\right)^{\left(\left\lvert T \right\rvert - 1\right)-k} \binom{\left\lvert T \right\rvert - 2}{k - 1} + \left(-1\right)^{\left(\left\lvert T \right\rvert - 1 \right) - \left(k - 1\right)} \binom{\left\lvert T \right\rvert - 2}{k - 2}$$
    接着搞一搞，就得到 $f_{i, j, k} = - f_{i - 1, j - p_i, k} + f_{i - 1, j - p_i, k - 1}$

所以 $f_{i, j, k} = f_{i - 1, j, k} - f_{i - 1, j - p_i, k} + f_{i - 1, j - p_i, k - 1}$

需要滚动数组，时间复杂度：$\Theta \left(n m k\right)$

代码

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom code.

// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;

// :\

tp qpow(tp x, tp y, tp mod);
tp inverse(tp x, tp mod) { return qpow(x, mod - 2, mod); }

// :/

constexpr tp mod = 998244353;

tp n, m, k, tar;
vector<tp> p;
vector<vector<tp>> f;

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  cin >> n >> k >> m;
  p.resize(n + 1);
  k = n - k + 1;
  f = vector<vector<tp>>(k + 1, vector<tp>(m + 1, 0));
  f[0][0] = 1;
  for (tp i = 1; i <= n; ++i) cin >> p[i];
  for (tp i = 1; i <= n; ++i) {
    for (tp l = m; l >= p[i]; --l) {
      for (tp j = k; j >= 1; --j)
        f[j][l] = (f[j][l] + f[j - 1][l - p[i]] - f[j][l - p[i]] + mod) % mod;
    }
  }
  for (tp i = 0; i <= m; ++i) tar = (tar + f[k][i] * inverse(i, mod)) % mod;
  cout << tar * m % mod << '\n';
}

void MIST() {
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
  static ifstream _in("input.txt");
  cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
  static ifstream _in(EFILE ".in");
  static ofstream _out(EFILE ".out");
  cin.rdbuf(_in.rdbuf());
  cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
  // cin >> _t;
  MIST();
  while (t < _t) STRUGGLING(++t);
  return 0;
}

// :\

tp qpow(tp x, tp y, tp mod) {
  tp tar = 1;
  while (y) {
    if (y & 1) tar = tar * x % mod;
    x = x * x % mod;
    y /= 2;
  }
  return tar;
}

//*/

暂无评论

发表评论