期望概率题选做

QOJ5468. 托卡马克

记 $F_m(z)$ 为最大高度不超过 $m$ 的路径生成函数（其中 $z$ 标志线段对数）。根据连分数理论，有：

$$F_m(z) = \frac{1}{1 - \frac{1 \cdot z}{1 - \frac{2 \cdot z}{\dots 1 - m \cdot z}}}$$

这个连分数能表达为两个多项式的比值 $F_m(z) = \frac{P_m(z)}{Q_m(z)}$。其分母满足递推式 $Q_m(z) = Q_{m-1}(z) - m z Q_{m-2}(z)$。
该递推关系刚好和 Hermite 多项式同构。能够得到其显式闭式解：

$$Q_m(z) = \sum_{j=0}^{\lfloor (m+1)/2 \rfloor} (-1)^j \frac{(m+1)!}{j! 2^j (m+1-2j)!} z^j$$

考虑求出分子 $P_m(z)$。分子度数最高不超过 $\lfloor m / 2 \rfloor$。注意到，当不限制最大高度时，所有路径生成函数为 $F_{\infty}(z) = \sum_{j=0}^{\infty} (2j-1)!! z^j$。因为受限高度 $m$ 和不受限的情况在前 $m$ 步是一模一样的，所以两者在模 $z^{m+1}$ 意义下同余。即：

$$\frac{P_m(z)}{Q_m(z)} \equiv F_{\infty}(z) \pmod{z^{m+1}} \implies P_m(z) \equiv Q_m(z) F_{\infty}(z) \pmod{z^{m+1}}$$

因为 $P_m(z)$ 实际度数仅为 $\lfloor m/2 \rfloor$，故我们只需要利用截断的 $F_{\infty}(z)$ 进行一次多项式乘法，就能精确求出分子 $P_m(z)$。

时间复杂度 $O(n \log n)$。

难度评测：Easy+

COCI 2016/2017 #7 F. Klavir

先说结论：

$$E(S) = \sum_{j \in \text{Borders}(S)} N^j$$

证明见 知乎上的一个回答

kmp 之后 dp 一下就做完了，时间复杂度 $O(n)$。

难度评测：不好评价

CTS2019. 氪金手游

先考虑在一组元素中，有一个元素 $u$ 最先被抽到，其概率恰好为 $\frac{W_u}{\sum_{x \in S} W_x}$。如果所有的偏序限制构成了一棵外向树，并且这棵树上的节点构成了集合 $S$，那么整个外向树的偏序同时成立的概率等于树中每个节点满足比其所有子孙节点先出现的概率的乘积：

$$P(\text{外向树}) = \prod_{u} \frac{W_u}{S_u}$$

其中，$S_u$ 为在这个外向树中，以 $u$ 为根的子树的所有节点的权值之和。

用容斥把树转化为若干外向树之后做背包，时间复杂度 $O(n^2)$

难度评测：Easy

GCJ 2014 Finals. ARAM

在状态 $u$ 下进入英雄选择阶段时，有两种操作：

1. 保留当前英雄 $i$：获得奖励 $P_i$，消耗掉一局游戏时间，下局开始时点数变为 $\min(C, u+1)$。
2. 重新抽取：仅当 $u \ge G$ 时可用，消耗 $G$ 点数，不消耗游戏时间，状态变为 $u-G$。

显然对于任意状态 $u \ge G$，我们一定会设定一个阈值，保留胜率前 $k_u$ 高的英雄，重新抽取剩下的 $N - k_u$ 个英雄。

高斯消元直接解线性方程可以通过 Subtask1。把高斯消元改成 SGS 可以获得满分，具体做法见 arXiv。

难度评测：Hard

NERC 2020 Online. Hit the Hay

这个题咱还不会 w

loj6874. zhylj 的抽卡

比较没意思的题。

设 $t_i$ 为物品 $i$ 的首次出现时间，有：
$$E(t_i) = \frac{1}{p_i}, \quad E(t_i^2) = \frac{2}{p_i^2} - \frac{1}{p_i}$$
对于 $i \neq j$ 的乘积期望 $E(t_i t_j)$，有：
$$E(t_i t_j) = \frac{1}{p_i p_j} - \frac{1}{p_i + p_j}$$

把式子拆开：

$$\bar{t} = \frac{1}{n}\sum_{i=1}^n t_i \implies E(\bar{t}) = \frac{1}{n} \sum_{i=1}^n \frac{1}{p_i}$$

对于方差 $\sigma^2$ 的期望：

$$E(\sigma^2) = \frac{1}{n} \sum_{i=1}^n E(t_i^2) - \frac{1}{n^2} E\left[\left(\sum_{i=1}^n t_i\right)^2\right] = \frac{n-1}{n^2} \sum_{i=1}^n E(t_i^2) - \frac{1}{n^2} \sum_{i \neq j} E(t_i t_j)$$

化简可得：

$$E(\sigma^2) = \frac{1}{n^2} \left( (2n-1)\sum_{i=1}^n \frac{1}{p_i^2} - (n-1)\sum_{i=1}^n \frac{1}{p_i} - \left(\sum_{i=1}^n \frac{1}{p_i}\right)^2 + \sum_{i \neq j} \frac{1}{p_i + p_j} \right)$$

注意到 $p_i = \frac{q_i}{S}$（其中 $S = \sum q_k$），前面的式子的大多数项可以直接线性计算。比较困难的是交叉项和 $\sum_{i \neq j} \frac{1}{p_i + p_j} = S \sum_{i \neq j} \frac{1}{q_i + q_j}$。

考虑构造多项式 $P(x) = \prod_{j=1}^n (x + q_j)$，其对数导数为：

$$\frac{P'(x)}{P(x)} = \sum_{j=1}^n \frac{1}{x + q_j}$$

令 $x = q_i$ 有：

$$\sum_{j \neq i} \frac{1}{q_i + q_j} = \frac{P'(q_i)}{P(q_i)} - \frac{1}{2q_i}$$

考虑对所有的 $i$ 计算出 $P(q_i)$ 和 $P'(q_i)$ 的值。注意到 $M(x) = \prod_{j=1}^n (x - q_j)$ 满足 $M(q_i) = 0$，令 $R(x) = P(x) - M(x)$，它的最高次项会被消去，度数为 $n-1$，且 $P(q_i) = R(q_i)$。

所以只需要在 $n$ 个点 $q_1, \dots, q_n$ 上计算 $R(x)$ 和 $P'(x)$，转置 NTT 多点求值可以做到 $O(n \log^2 n)$。

难度评测：Medium

CF1924E. Paper Cutting Again

原问题显然等价于将初始的 $n-1$ 条垂直线（集合 $V$）和 $m-1$ 条水平线（集合 $H$）进行随机全排列，我们按排列顺序检查每一条线，如果这条线还没有被丢弃，则进行切割，并丢弃比它编号更大的线。

状态 $(x, y)$ 被访问当且仅当它成为某一时刻的双重下界，我们考虑如下分类讨论：

• $(n, m)$：显然概率为 $1$。
• $(n, y)$ （$y < m$）：在排列中，线 $y \in H$ 必须出现在所有的 $V$ 以及所有的 $\{1, \dots, y-1\} \subset H$ 之前。相关元素的总数为 $(n-1) + (y-1) + 1 = n+y-1$。概率为： $$P(n, y) = \frac{1}{n+y-1}$$
• $(x, m)$ （$x < n$）：根据对称性，概率为： $$P(x, m) = \frac{1}{x+m-1}$$
• $(x, y)$ （$x < n, y < m$）：$x$ 和 $y$ 必须是各自集合中的历史最小值。在排列中，$x$ 和 $y$ 这两个元素必须排在所有 $V_{<x}$ 和 $H_{<y}$ 之前。相关元素总数为 $(x-1) + (y-1) + 2 = x+y$。它们占据前两名的概率为： $$P(x, y) = \frac{2}{(x+y)(x+y-1)} = \frac{2}{x+y-1} - \frac{2}{x+y}$$

期望步数为上述所有满足 $x \cdot y \ge k$ 的状态概率之和，时间复杂度线性。

难度评测：Easy+

ARC136F. Flip Cells

绝世好题，这里给一个和官方题解完全不同的线性代数做法。

我们将每一行 1 的数量记录下来，构成状态向量 $\mathbf{c} = (c_1, c_2, \dots, c_H)$，其中 $c_i \in [0, W]$ 表示第 $i$ 行当前 1 的个数。初始状态为 $\mathbf{C}$，目标状态为 $\mathbf{A}$。

每次操作以等价为以 $\frac{1}{H}$ 的概率选中第 $i$ 行，然后在该行以 $\frac{c_i}{W}$ 的概率将 1 翻转为 0，以 $\frac{W-c_i}{W}$ 的概率将 0 翻转为 1，显然每行是独立的。

对于每一行，它的转移矩阵 $M$ 拥有 $W+1$ 个特征值，分别为：

$$\lambda_k = 1 - \frac{2k}{W} \quad (k = 0, 1, \dots, W)$$

其对应的右特征向量是 Krawtchouk 多项式 $K_k(c)$：

$$K_k(c) = \sum_{j=0}^k (-1)^j \binom{c}{j} \binom{W-c}{k-j}$$

该特征向量在权重 $\pi(c) = \binom{W}{c} 2^{-W}$ 下是正交的，满足 $\sum_{c=0}^W \pi(c) K_k(c) K_l(c) = \binom{W}{k} \delta_{k, l}$。

注意到全局的转移矩阵可以看作各行转移矩阵的组合，全局特征向量是各行特征向量的张量积：

$$K_{\mathbf{k}}(\mathbf{c}) = \prod_{i=1}^H K_{k_i}(c_i) \quad \text{其中 } \mathbf{k} = (k_1, k_2, \dots, k_H)$$

对应的全局特征值为：

$$\Lambda_{\mathbf{k}} = \frac{1}{H} \sum_{i=1}^H \lambda_{k_i} = 1 - \frac{2}{HW} \sum_{i=1}^H k_i$$

对于可逆马尔可夫链，从初始状态 $\mathbf{C}$ 到达目标状态 $\mathbf{A}$ 的期望步数 $E_{\mathbf{C}}$ 有正交基展开公式：

$$E_{\mathbf{C}} = \sum_{\mathbf{k} \neq \mathbf{0}} \frac{K_{\mathbf{k}}(\mathbf{A})^2 - K_{\mathbf{k}}(\mathbf{C}) K_{\mathbf{k}}(\mathbf{A})}{N_{\mathbf{k}} (1 - \Lambda_{\mathbf{k}})}$$

其中 $N_{\mathbf{k}} = \prod_{i=1}^H \binom{W}{k_i}$ 为内积的模长。

将 $1 - \Lambda_{\mathbf{k}} = \frac{2}{HW} \sum_{i=1}^H k_i$ 代入，令 $S = \sum_{i=1}^H k_i$，式子可以拆分为对每一行的乘积：

$$E_{\mathbf{C}} = \frac{HW}{2} \sum_{S=1}^{HW} \frac{1}{S} \sum_{\sum k_i = S} \left( \prod_{i=1}^H \frac{K_{k_i}(A_i)^2}{\binom{W}{k_i}} - \prod_{i=1}^H \frac{K_{k_i}(A_i)K_{k_i}(C_i)}{\binom{W}{k_i}} \right)$$

为此，对于第 $i$ 行，分别构造两个多项式：

$$P_{U_i}(x) = \sum_{k=0}^W \left( \frac{K_k(A_i)^2}{\binom{W}{k}} \right) x^k$$ $$P_{V_i}(x) = \sum_{k=0}^W \left( \frac{K_k(A_i)K_k(C_i)}{\binom{W}{k}} \right) x^k$$

我们只需求出这 $H$ 个 $P_U(x)$ 的乘积多项式 $F(x)$，以及这 $H$ 个 $P_V(x)$ 的乘积多项式 $G(x)$。
最后，答案即为：

$$E_{\mathbf{C}} = \frac{HW}{2} \sum_{S=1}^{HW} \frac{[x^S]F(x) - [x^S]G(x)}{S} \pmod{998244353}$$

难度评测：Hard

P7437. 既见君子

典题，显然分母就是原图生成树，可以直接矩阵树定理求，分子是经过 $z$ 的生成树个数，高斯消元做就好了。

难度评测：Easy

CF1866M. Mighty Rock Tower

定义 $D_x = f_x - f_{x-1}$。显然：

$$D_x = 1 + \sum_{k=1}^{x-1} p_x^k(1-p_x) (f_x - f_{x-k}) + p_x^x (f_x - f_0)$$

将 $f_x - f_{x-k} = \sum_{i=1}^k D_{x-i+1}$ 代入，化简为：

$$D_x = 1 + \sum_{y=1}^x p_x^{x-y+1} D_y$$

把等式右侧的 $y=x$ 这一项 $p_x D_x$ 移到左边得到：

$$D_x = \frac{1 + \sum_{y=1}^{x-1} p_x^{x-y+1} D_y}{1 - p_x}$$

观察分子中的求和部分 $S(x) = \sum_{y=1}^{x-1} p_x^{x-y+1} D_y$。如果底数 $p_x$ 固定为 $p$，可以发现：

$$S_p(x) = \sum_{y=1}^{x-1} p^{x-y+1} D_y = p \cdot S_p(x-1) + p^2 D_{x-1}$$

时间复杂度 $O(n)$。

难度评测：Easy

MX-NOI 模拟赛 4 T2.

这个题咱还不会 w 现在会了。

首先可以发现如果区间 $[i,j]$、$[t,k]$（$i \le t \le j \le k$）都是好的，那么区间 $[i,k]$ 也是好的。

那么设 $r_i$ 为以 $i$ 为左端点的最长的好的区间的右端点。

设 $l_i$ 表示最大的 $j$ 使得 $r_j \ge r_i$（$j < i$），考虑建出一棵树，节点 $i$ 的父亲是 $l_i$。如果 $l_i$ 不存在，则设 $0$ 节点为其父亲。可以发现树上一对有祖先关系的节点即对应了原区间中的一个好区间。

同时注意到

$$\left(\sum_{i=l}^k c_i\right) > c_{k+1}$$

是否成立其实只和 $i-1$、$k$、$k+1$ 这三个位置是否操作有关。

考虑按树的结构进行 dp，设

$$dp_{l,r,f_1,f_2,f_3,f_4}$$

表示当前子树的根是 $l$，其子树中包含了 $[l,r)$ 中的节点，和 $l-1,l,r-1,r$ 这四个位置的操作情况。dp 的值是区间 $[l,r)$ 的所有操作情况的子区间的贡献之和。

转移考虑枚举一个 $i$（$l<i<r$）作为节点 $l$ 剩余儿子中最大的一个，同时枚举 $i_1,i_2$ 表示位置 $i-1,i$ 的操作情况，此时要求的是 $[l,i]$ 这个区间是好的，且区间 $[i,r]$ 不是好的。这里因为问题还会被递归到 $[l,i)$、$[i,r)$ 的两个子问题，可以证明其余的位置只要在子问题中合法，在当前情况一定合法。答案记得乘上系数 $k^{r-i}$。

时间复杂度 $O(n^3)$。

难度评测：Hard-

CF1450H2. Multithreading (Hard Version)

这题也太牛了。

对于给定的一种合法染色方案，匹配时异色交点对数的最小值为：

$$f(c) = \frac{1}{2} \left| b_e - b_o \right|$$

其中 $b_e$ 和 $b_o$ 分别是偶数位置和奇数位置上的黑色线轴数量。
由于总数为偶数，必定有 $b_e + w_e = \frac{n}{2}$，$b_o + w_o = \frac{n}{2}$，所以式子等价于：

$$f(c) = \frac{1}{2} \left| b_e + w_o - \frac{n}{2} \right|$$

这意味着只需要考虑在偶数位置为 b 以及在奇数位置为 w 的数量。

假设当前未确定的线轴共有 $k$ 个。因为保证最终 $b$ 的总数为偶数，在所有 $2^k$ 种填法中，恰有一半会产生合法的染色。因此，期望值为所有合法状态的 $f(c)$ 之和除以 $2^{k-1}$，等价于求所有组合中 $f(c)$ 两倍的绝对值之和，最后除以 $2^k$。

设已有确定字符的贡献和为 $C$，未确定位置中同样做出该选择的个数为 $i$ ($0 \le i \le k$)。令 $D = C - \frac{n}{2}$，则答案就是：

$$Ans = \frac{1}{2^k} \sum_{i=0}^k \binom{k}{i} [ i \equiv D \pmod 2 ] |i + D|$$

考虑去掉绝对值。如果 $D \ge 0$，由于 $i \ge 0$，绝对值可直接去掉，化简后得到：

$$Tot(k, D) = \sum_{i=0}^k \binom{k}{i} [ i \equiv D \pmod 2 ] (i + D) = k \cdot 2^{k-2} + D \cdot 2^{k-1} \quad (k \ge 2)$$

若 $D < 0$，除了基础的 $Tot(k, D)$ 之外，对于那些使 $i+D < 0$ 的项，我们需要额外加上两倍它的相反数来进行补偿。设 $R = -D$，这一补偿项为：

$$2 \sum_{i=0}^R \binom{k}{i} [i \equiv R \pmod 2] (R - i)$$

上式可表示为：

$$2 \left( R \cdot Y(k, R) - k \cdot Y(k-1, R-1) \right)$$

其中 $Y(n, m) = \sum_{i=0}^m \binom{n}{i} [i \equiv m \pmod 2]$。

利用组合恒等式，可以证明：

$$Y(n, m) = \sum_{i=0}^m \binom{n-1}{i} = B(n-1, m)$$

这里 $B(N, M)$ 是最普通的二项式前缀和。

修改的时候显然存在结论：

• $B(N, M+1) = B(N, M) + \binom{N}{M+1}$
• $B(N, M-1) = B(N, M) - \binom{N}{M}$
• $B(N+1, M) = 2 B(N, M) - \binom{N}{M}$
• $B(N-1, M) = \frac{1}{2}\left(B(N, M) + \binom{N-1}{M}\right)$

用三个指针维护一下就好了，时间复杂度 $O(n+m)$。

难度评测：Medium+

NAC2020 D. All Kill

$$\begin{aligned} & \Omega = \Big\{ (T_1, \dots, T_n) \in \{1, \dots, t\}^n \text{} \Big\} \\ \\ & I_i = [S_i, S_i + c_i - 1] \quad (i \in \{1, \dots, n\}) \\ \\ & (T_1, \dots, T_n) \in \Omega \iff \begin{cases} S_i + c_i - 1 \le t, & \forall i \in \{1, \dots, n\} \\ T_j \notin I_i, & \forall j < i \end{cases} \\ \\ & R_k = \sum_{j=n-k+1}^n c_j \quad (k \in \{1, \dots, n\}) \\ \\ & |\{T_n\}| = t - c_n + 1 = t - R_1 + 1 \\ \\ & |\{T_{n-k+1} \mid T_{n}, \dots, T_{n-k+2}\}| = (t - R_{k-1}) - c_{n-k+1} + k \\ & |\{T_{n-k+1} \mid T_{n}, \dots, T_{n-k+2}\}| = t - R_k + k \quad (k \in \{2, \dots, n\}) \\ \\ & |\Omega| = |\{T_n\}| \cdot \prod_{k=2}^{n} |\{T_{n-k+1} \mid T_{n}, \dots, T_{n-k+2}\}| \\ \\ & |\Omega| = (t - R_1 + 1) \prod_{k=2}^{n} (t - R_k + k) \\ \\ & |\Omega| = (t - R_n + 1) \prod_{k=1}^{n-1} (t - R_k + k + 1) \\ \\ & S_n = R_n = \sum_{j=1}^n c_j \\ \\ & p \cdot t^n = |\Omega| = (t - S_n + 1) \prod_{i=1}^{n-1} (t - R_i + i + 1) \pmod{998244353} \end{aligned}$$

时间复杂度 $O(n)$。

难度评测：Easy+

PA2025. Egzamin

定义 $f_j$ 表示在前 $i$ 道题中，恰好答对 $j$ 道题的概率，显然：

$$f_j = f_{k-1} * p_i + f_j * (1 - f_i)$$

这是一个经典的泊松二项分布，所以答对题目的数量大致符合正态分布，方差最大为 $\frac{N}{4} = 12500$，标准差 $\sigma \approx 111$，转移的时候维护一下有效概率区间 $[L,R]$ 就做完了。时间复杂度我不会证，但是应该是 $O(n \sqrt n)$ 左右吧。

难度评测：Medium-

AGC032F. One Third

虽然这个题很牛，但是我真的很讨厌做代数几何。

这里给一个不需要几何或者积分基础，完全凭感觉的做法。

考虑将披萨的周长标准化为 $1$。切 $N$ 刀等价于在一个周长为 $1$ 的圆上，独立且均匀随机地投下 $N$ 个点 $P_1, P_2, \dots, P_N \in [0, 1)$。

直接在周长为 $1$ 的大圆上处理 $|x - 1/3|$ 比较困难。我们考虑 $|x - 1/3|$ 的几何意义其实表示的是大圆上某一点 $P_i$，与另一点 $P_j$ 顺时针（或逆时针）旋转 $1/3$ 后的位置之间的最短距离。

为了消除这个 $1/3$ 的偏移量，想象把这个周长为 $1$ 的大圆，紧紧地缠绕在一个周长为 $1/3$ 的小圆上，正好缠绕 $3$ 圈。此时，原圆上的任意点 $P_i$ 在小圆上的坐标为：

$$X_i = P_i \bmod (1/3)$$

同时，为了记住这个点原本属于哪一圈，我们给它打上一个标签：

$$C_i = \lfloor 3 P_i \rfloor \in \{0, 1, 2\}$$

现在，这 $N$ 个点落在了周长为 $1/3$ 的小圆上，把小圆分割成了 $N$ 段弧。设我们将这 $N$ 个点在小圆上顺时针排序，它们之间的 $N$ 段弧长依次为 $g_1, g_2, \dots, g_N$，显然有 $\sum_{k=1}^N g_k = 1/3$。

观察一下小圆上的每一段弧 $g_k$。它连接了小圆上的相邻两点，设起点标签为 $c_A$，终点标签为 $c_B$，这段弧 $g_k$ 代表了大圆上两个点在去除了若干个 $1/3$ 之后的纯粹距离。

• 如果 $c_A = c_B$，说明这两个点在同一圈，它们在大圆上的真实距离就是 $g_k$。但我们需要的是靠近 $1/3$ 的距离，所以这不是我们想要的。
• 如果 $c_A \neq c_B$，说明这两个点在大圆上跨越了不同的圈，它们在大圆上的真实距离恰好是 $1/3 + g_k$ 或 $1/3 - g_k$ 乃至 $2/3 \pm g_k$。此时，$g_k$ 恰好就是绝对值误差 $|x - 1/3|$。

所以其实就是小圆上所有两端点标签不同的弧 $g_k$ 中的最小值。

为了严格描述标签的变化，我们定义第 $k$ 段弧的标签变化（差值）为 $D_k$。

如果我们把所有 $D_k$ 加起来，相当于绕小圆走了一整圈，大圆上对应走过了 $1/3$ 的长度。因此，必定有：

$$\sum_{k=1}^N D_k \equiv 1 \pmod 3$$

由于投点是完全随机的，所以这 $N$ 个差值 $D_1, D_2, \dots, D_N \in \{0, 1, 2\}$ 是独立均匀分布的，只要满足它们的和模 $3$ 余 $1$ 即可。这样的序列 $D$ 共有 $3^{N-1}$ 种。

假设在某种序列 $D$ 中，有恰好 $K$ 个非零项。这意味着在 $N$ 段总长为 $1/3$ 的弧中，有 $K$ 段是我们要找的有效弧。

$$\begin{aligned} E &= \sum_{K=1}^N P(K) \times E(K) \\ &= \sum_{K=1}^N \frac{\binom{N}{K} A_K}{3^{N-1}} \times \frac{1}{3KN} \\ &= \sum_{K=1}^N \frac{\binom{N}{K} \frac{2^K - (-1)^K}{3}}{3^{N-1}} \times \frac{1}{3KN} \\ &= \frac{1}{N \cdot 3^{N+1}} \sum_{K=1}^N \binom{N}{K} \frac{2^K - (-1)^K}{K} \end{aligned}$$

其中 $P(K)$ 为恰好有 $K$ 个非零项的概率，时间复杂度 $O(n)$。

难度评测：Hard-

CTSC2017. 游戏

小 R 每局获胜与否仅与前一局的结果相关，因此构成了一个一阶马尔可夫链，特定对局的结果将整个 $n$ 局的序列切分成了多个相互独立的区间。

对于一个被固定点 $L$ 和 $R$ 夹在中间的开区间 $(L, R)$（其两端取值分别为 $c_L, c_R$）考虑计算区间内部的期望和：$E_{\sum_{i=L+1}^{R-1} S_i \mid S_L=c_L, S_R=c_R}$。

显然我们有：

$$E_{\text{Sum} \mid S_R=c_R} = \frac{E_{\text{Sum} \wedge (S_R=c_R)}}{P(S_R=c_R)}$$

构建一组状态：$P_0, P_1$ 分别表示当前局小 B 和小 R 获胜的概率。$E_0, E_1$ 分别表示在当前局小 B 和小 R 获胜的情况下，当前区间已累加胜场的期望。

由第 $i-1$ 局转移到第 $i$ 局，转移如下：

• $P_{0}' = P_0(1-q_i) + P_1(1-p_i)$
• $P_{1}' = P_0 q_i + P_1 p_i$
• $E_{0}' = E_0(1-q_i) + E_1(1-p_i)$
• $E_{1}' = E_0 q_i + E_1 p_i + P_{1}'$

这个转移显然可以用矩阵维护，时间复杂度 $O(n+m \log n+m \log m)$

难度评测：Easy