洛谷 9621 下次再见 题解

发表于 分类于

思路

不妨令 pip_i 表示圆圈 ii MISS 的概率，eie_i 为圆圈 ii 的期望得分．下文称“强制退出游戏”为“寄”．

先考虑固定起点为 11 怎么做．

设 fif_i 表示点击圆圈 ii 后寄了的概率，gig_i 表示点击完前 ii 个圆圈后没寄的概率．

考虑计算 ff，此时 (i−K,i](i - K, i] 这一段圆圈必须全都 MISS，而圆圈 i−Ki - K 不能 MISS，且点击 i−Ki - K 前没寄．所以有：

fi=((1−pi−K)∏j∈(i−K,i]pj)gi−K−1f_i = \left((1 - p_{i - K}) \prod_{j \in (i - K, i]} p_j\right) g_{i - K - 1}

考虑计算 gg，此时对于前 ii 个圆圈，点击后都不能寄，有：

gi=1−∑j=1ifjg_i = 1 - \sum_{j = 1}^i f_j

此时期望得分为

e1+∑i=1n−1giei+1e_1 + \sum_{i = 1}^{n - 1} g_i e_{i + 1}

现在考虑对于 1∼n1 \sim n 中所有位置作为起点时，计算答案．不妨先算出期望分数的和，然后乘 1n\frac{1}{n}．

类似地，设 fs,if_{s, i} 表示从圆圈 ss 开始游玩，点击圆圈 ii 后寄了的概率，gs,ig_{s, i} 表示从圆圈 11 开始游玩，点击完圆圈 ii 后继续游玩的概率，特别地，令 gs,s−1=1g_{s, s - 1} = 1．那么期望和为：

∑s=1n(es+∑i=sn−1gs,iei+1)=∑i=1nei(1+∑s=1i−1gs,i−1)\begin{aligned} \sum_{s = 1}^n \left(e_s + \sum_{i = s}^{n - 1} g_{s, i} e_{i + 1}\right) &= \sum_{i = 1}^n e_i \left(1 + \sum_{s = 1}^{i - 1} g_{s, i - 1}\right) \\ \end{aligned}

不妨令 hi=∑s=1igs,i=i−∑j=1i∑s=1jfs,jh_i = \sum\limits_{s = 1}^i g_{s, i} = i - \sum\limits_{j = 1}^i \sum\limits_{s = 1}^j f_{s, j}，考虑对每个 ii 快速计算 ∑s=1ifs,i\sum\limits_{s = 1}^i f_{s, i}．

∑s=1ifs,i=∑s=1i((1−pi−K)∏j∈(i−K,i]pj)gs,i−K−1=((1−pi−K)∏j∈(i−K,i]pj)∑s=1igs,i−K−1=((1−pi−K)∏j∈(i−K,i]pj)hi−K−1\begin{aligned} \sum_{s = 1}^i f_{s, i} &= \sum_{s = 1}^i \left((1 - p_{i - K}) \prod_{j \in (i - K, i]} p_j\right) g_{s, i - K - 1} \\ &= \left((1 - p_{i - K}) \prod_{j \in (i - K, i]} p_j\right) \sum_{s = 1}^i g_{s, i - K - 1} \\ &= \left((1 - p_{i - K}) \prod_{j \in (i - K, i]} p_j\right) h_{i - K - 1} \end{aligned}

预处理前缀积和及其逆元即可 O(n)O(n) 计算．注意 pip_i 可以等于 00，std 的处理方式是使用 11 作为占位，然后特判 (i−K,i](i - K, i] 中有 00 的情况．

代码

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
#include <cstdio>
#define debug(...) fprintf(stderr, __VA_ARGS__)

using i64 = long long;

inline i64 rd() {
  i64 x = 0, f = 1, c = getchar();
  while (((c - '0') | ('9' - c)) < 0)
    f = c != '-', c = getchar();
  while (((c - '0') | ('9' - c)) > 0)
    x = x * 10 + c - '0', c = getchar();
  return f ? x : -x;
}

struct Gen {
  using ull = unsigned long long;
  ull rand_num;
  inline void init(ull seed) { rand_num = seed; }
  inline ull next() {
    ull z = (rand_num += 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
  }
  inline int rnr(int l, int r) { return l + (int)(next() % (r - l + 1)); }
  inline void get(int &a, int &b, int &c, int &d) {
    int divpart = rnr(0, 100);
    a = rnr(0, divpart), b = divpart - a;
    c = rnr(0, 100 - divpart), d = 100 - divpart - c;
  }
} Ge;

const int N = 5e6;
const i64 P = 998244353;
inline i64 fpow(i64 b, i64 p) {
  i64 res = 1;
  for (; p; b = b * b % P, p >>= 1) {
    if (p & 1) res = res * b % P;
  }
  return res;
}
i64 I[101];

int type;
int n, k;
i64 e[N + 5], p[N + 5], ip[N + 5];
i64 pr[N + 5], ipr[N + 5];
int fl[N + 5];
i64 f[N + 5];

int main() {
  for (int i = 1; i <= 100; i++) I[i] = fpow(i, P - 2);

  type = rd(), Ge.init(rd());
  n = rd(), k = rd();
  for (int i = 1, p1, p2, p3, p4; i <= n; i++) {
    if (!type) p1 = rd(), p2 = rd(), p3 = rd(), p4 = rd();
    else Ge.get(p1, p2, p3, p4);
    e[i] = (300 * p1 + 100 * p2 + 50 * p3) % P * I[100] % P;
    p[i] = p4 * I[100] % P, ip[i] = 100 * I[p4] % P;
  }

  pr[0] = ipr[0] = 1;
  for (int i = 1; i <= n; i++) {
    pr[i] = pr[i - 1] * (p[i] ? p[i] : 1) % P;
    ipr[i] = ipr[i - 1] * (ip[i] ? ip[i] : 1) % P;
    fl[i] = fl[i - 1] + !p[i];
  }

  i64 sum = 0;
  for (int i = 1; i <= n; i++) {
    i64 ct = 0;

    if (i >= k) {
      i64 c1 = (fl[i] - fl[i - k]) ? 0 : (pr[i] * ipr[i - k] % P);
      i64 c2 = (1 + P - p[i - k]) % P;

      (ct += c1) %= P;
      if (i > k) (ct += c1 * c2 % P) %= P;
      if (i > k + 1) (ct += c1 * c2 % P * f[i - k - 1] % P) %= P;
    }

    (sum += ct) %= P;
    f[i] = (i + P - sum) % P;
  }

  i64 ans = 0;
  for (int i = 1; i <= n; i++) (ans += (1 + f[i - 1]) * e[i] % P) %= P;
  (ans *= fpow(n, P - 2)) %= P;

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

参考

edisnimorF, 下次再见 题解