LibreOJ 2541 「PKUWC2018」猎人杀

发表于 | 分类于

Description

有\(n\)个人，第\(i\)人有一个正整数权值\(w_i\)。

每个人死后要开枪打死另一个人，假设剩下的人权值和为\(S\)，那么编号为\(i\)的活人被选中的概率为\(\frac{w_i}{S}\)。至于第一枪的话，随机选择一个人，第\(i\)个人被选中的概率为\(\frac{w_i}{\sum_{i = 1}^nw_i}\)。

问编号为\(1\)的人有多少概率成为最后一个死的人。

\(\sum_{i = 1}^n w_i\leq 10^5\)。

Solution

这思路ao神，，，

一个非常毒瘤的事情是每个人被打死的概率都在时刻变动，我们考虑让每个人被击中的概率不变。

这样的话我们规定可以向死人开枪，但是一个人不能死两次（大雾），但他可以接着往下开枪。这样的话其实和原来的模型是一样的，下面证明一下：

首先先说一个引理吧：级数\(\sum_{i = 0}^{+\infty} a^ig=\frac{g}{1 - a}(0\leq a<1)\)。

证明倒还简单。把\(g\)提出来，然后后面用等比数列求和公式可以得到\(\frac{1-a^{\infty}}{1-a}\)，而\(\lim_{x\rightarrow +\infty} a^x = 0(0\leq a < 1)\)，带回去就得到了\(\frac{1}{1-a}\)，乘上\(g\)就是\(\frac{g}{1-a}\)。

然后我们考虑假设现在死掉的人的权值和为\(T\)，总权值和为\(S\)。那么下一个死掉的人是\(i\)的概率就是： \[ \sum_{k = 0}^{\infty} (\frac{T}{S})^k\frac{w_i}{S} \] 应用上面的结论，这个东西可以化简为\(\frac{w_i}{S}\cdot\frac{S}{S - T} = \frac{w_i}{S - T}\)，正是我们想要的那个概率……

但接下来还不好做……然后我们想一想我们直接做是要求了恰好0个人在\(1\)之后死，那要是我们求至少\(k\)个人在\(1\)之后死呢？

假设这\(k\)个人的权值和为\(T\)，总权值和为\(S\)。那么这个集合对答案的贡献为： \[ (-1)^k\sum_{i = 0}^{\infty}(1 - \frac{T + w_1}{S})^i \frac{w_1}{S} \] 前面的\((-1)^k\)是容斥系数，然后后面的级数又可以应用上面的引理了！这次可以推出来后面的级数为\(\frac{w_1}{T + w_1}\)。

虽然推出来了式子，不过我们总不能枚举子集再容斥吧？注意到如果两个集合\(T\)一样的话，那么他们（不考虑容斥系数的话）对答案贡献一样。所以我们考虑如何去搞每个\(T\)的所有对应集合的容斥系数之和就行了，这个东西的生成函数显然是： \[ \prod_{i = 2}^n(1-x^{w_i}) \] 然后这玩意就是分治FFT的经典题了……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <memory>
#include <vector>
using ll = long long;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int f = flip(bi, i);
    if(f < i) std::swap(A[f], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi_n = inv(xi_n);
    for(int i = 0; i < n; i += (L << 1)) {
      ll xi = 1;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (y * xi) % ha) % ha;
        A[j + L] = (x - (y * xi) % ha + ha) % ha;
        xi = xi * xi_n % ha;
      }
    }
  }
  if(flag) {
    ll inv_n = inv(n);
    for(int i = 0; i < n; i ++) {
      A[i] = A[i] * inv_n % ha;
    }
  }
}

struct Poly {
  ll *A; int n;
  Poly(int len) {
    A = (ll*)calloc(len + 1, sizeof(ll));
    n = len;
  }
  ~Poly() { free(A); }
};
const int maxn = 100005;
int n; int w[maxn];
Poly *div_con(int L, int R) {
  if(L == R) {
    Poly *ret = new Poly(w[L]);
    ret -> A[0] = 1; ret -> A[w[L]] = ha - 1LL;
    return ret;
  } else {
    static ll A[maxn << 2], B[maxn << 2];
    int M = (L + R) / 2;
    Poly *l = div_con(L, M), *r = div_con(M + 1, R);
    int rn = l -> n + r -> n;
    int bi = 0, len = 1;
    while(len <= rn) {
      len <<= 1; bi ++;
    }
    std::copy((l -> A), (l -> A) + l -> n + 1, A);
    std::copy((r -> A), (r -> A) + r -> n + 1, B);
    std::fill(A + l -> n + 1, A + len, 0LL);
    std::fill(B + r -> n + 1, B + len, 0LL);
    delete l; delete r;
    NTT(A, bi); NTT(B, bi);
    for(int i = 0; i < len; i ++) A[i] = A[i] * B[i] % ha;
    NTT(A, bi, true);
    Poly *ret = new Poly(rn);
    std::copy(A, A + rn + 1, ret -> A);
    return ret;
  }
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
  Poly *P = div_con(2, n);
  ll *A = P -> A; int len = P -> n;
  ll ans = 0;
  for(int i = 0; i <= len; i ++) {
    ll delta = A[i];
    delta = delta * (ll(w[1])) % ha;
    delta = delta * inv(w[1] + i) % ha;
    ans = (ans + delta) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}