「PKUWC2018」猎人杀 题解

---

题目链接

• https://loj.ac/problem/2541

这是一道经常被拿出来四处安利的题 (

解题思路

对于某一个时刻, 记 $f_i$ 为第 $i$ 个猎人当前没有死亡, 且在下一次开枪后死亡的概率. 同时, 记 $m$ 为所有猎人 $w_i$ 之和, $d$ 为已死亡猎人之和. 则有

$$f_i = \frac{w_i}{m - d}$$

容易得到

$$f_i = \frac{w_i}{m} + \frac{d}{m} f_i$$

考虑这个式子的实际意义. 即如果向已死亡的猎人射击, 等同于再次射击… 也就是在一猎人死亡后, 仍可认为其能被作为射击目标. 在该意义下计算并不会影响 $f_i$ 的值.

现在要解决的问题即为, 求恰好 $0$ 人在 $1$ 死亡之后死亡概率. 考虑容斥, 枚举在 $1$ 死亡后存活的猎人集合 $S$, 同时记 $s$ 为集合 $S$ 中的猎人 $w_i$ 之和. 可以得到答案为

$$\sum_{S} (-1) ^ {|S|} \sum_{t = 0} ^ \infty (1 - \frac{s + w_1}{m}) ^ t \cdot \frac{w_1}{m} = \sum_{S} (-1) ^ {|S|} \frac{w_1}{s + w_1}$$

笼统解释一下, 集合 $S$ 中猎人要能在 $1$ 之后存活, 其划分界限一定为 $1$ 死亡的时刻, 并在该时刻前 $S$ 和 $1$ 都不能死亡. 后者利用广义二项式定理即可得出.

显然枚举集合是不科学的. 注意到 $\sum w_i$ 的值不大, 求出每一个 $s$ 对应的集合容斥系数之和即可. 其生成函数为

$$F(x) = \prod_{i = 2} ^ n \left(1 - x ^ {w_i} \right)$$

分治 FFT 计算即可. 最终的答案为

$$\sum_{s \ge 0} [x ^ s] F(x) \cdot \frac{w_1}{s + w_1}$$

记 $m = \sum\limits_{i = 1} ^ n w_i$, 则时间复杂度为 $O(m \log ^ 2 m)$.

代码实现

用 vector 代替数组写多项式果然快乐 (

// LOJ #2541
// DeP
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int LOG = 18, MAXN = 1 << LOG | 1, P = 998244353, G = 3;

int W[LOG][MAXN];

int fpow(int base, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) ret = 1LL * ret * base % P;
    base = 1LL * base * base % P, b >>= 1;
  }
  return ret;
}

namespace Poly {
  int r[MAXN];
  inline void init(const int& Lim, const int& L) {
    for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
  }

  void NTT(int* f, const int& Lim, const int& type) {
    for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
    for (int k = 0, Mid = 1; Mid < Lim; Mid <<= 1, ++k) {
      const int* w = W[k];
      for (int i = 0; i < Lim; i += Mid << 1)
        for (int j = 0; j < Mid; ++j) {
          int f0 = f[i+j], f1 = 1LL * w[j] * f[i+j+Mid] % P;
          f[i+j] = (f0 + f1) % P, f[i+j+Mid] = (f0 - f1 + P) % P;
        }
    }
    if (type < 0) {
      int iv = fpow(Lim, P - 2);
      for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * iv % P;
      reverse(f + 1, f + Lim);
    }
  }
}

void PolyPre() {
  for (int w, i = 0, Mid = 1; i < LOG; ++i, Mid <<= 1) {
    W[i][0] = 1, w = fpow(G, (P - 1) / (Mid << 1));
    for (int j = 1; j < Mid; ++j)
      W[i][j] = 1LL * w * W[i][j - 1] % P;
  }
}

typedef vector<int> poly;

poly operator * (const poly& f, const poly& g) {
  static int A[MAXN], B[MAXN];
  int Lim = 1, L = 0;
  while (Lim < int(f.size() + g.size())) Lim <<= 1, ++L;
  for (int i = 0; i < Lim; ++i) {
    A[i] = (i < (int) f.size())? f[i]: 0;
    B[i] = (i < (int) g.size())? g[i]: 0;
  }
  Poly::init(Lim, L), Poly::NTT(A, Lim, 1), Poly::NTT(B, Lim, 1);
  for (int i = 0; i < Lim; ++i) A[i] = 1LL * A[i] * B[i] % P;
  Poly::NTT(A, Lim, -1);
  poly h(f.size() + g.size() - 1);
  for (size_t i = 0; i < h.size(); ++i) h[i] = A[i];
  return h;
}

int n;
int w[MAXN];

poly solve(int L, int R) {
  if (L == R) {
    poly g(w[L] + 1);
    return g[0] = 1, g[w[L]] = P - 1, g;
  }
  int Mid = (L + R) / 2;
  return solve(L, Mid) * solve(Mid + 1, R);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", w + i);

  PolyPre();
  poly f = solve(2, n);
  int ans = 0;
  for (int i = 0; i < (int) f.size(); ++i) {
    int iv = fpow((i + w[1]) % P, P - 2);
    ans = (ans + 1LL * w[1] * f[i] % P * iv % P) % P;
  }

  printf("%d\n", ans);
  return 0;
}

参考资料

• danihao123, LibreOJ 2541 「PKUWC2018」猎人杀
• zjp-shadow, LOJ #2541. 「PKUWC 2018」猎人杀(容斥, 期望dp, NTT优化)

---