2263 「CTSC2017」游戏

小 R 和室友小 B 在寝室里玩游戏。他们一共玩了 $ n $ 局游戏，每局游戏的结果要么是小 R 获胜，要么是小 B 获胜。 第 $ 1 $ 局游戏小 R 获胜的概率是 $ p_1 $，小 B 获胜的概率是 $ 1 - p_1 $。除了第一局游戏之外，每一局游戏小 R 获胜的概率与上一局游戏小 R 是否获胜有关。 具体来说： 1. 如果第 $ i − 1 (1 < i \leq n) $ 局游戏小 R 获胜，那么第 $ i $ 局游戏小 R 获胜的概率为 $ p_i $，小 B 获胜的概率为 $ 1 - p_i $。 2. 如果第 $ i − 1 (1 < i \leq n) $ 局游戏小 B 获胜，那么第 $ i $ 局游戏小 R 获胜的概率为 $ q_i $，小 B 获胜的概率为 $ 1 - q_i $。 小 D 时常过来看小 R 和小 B 玩游戏，因此他知道某几局游戏的结果。他想知道在他已知信息的条件下，小 R 在 $ n $ 局游戏中总共获胜的局数的期望是多少。 小 D 记性不太好，有时他会回忆起某局游戏的结果，并把它加入到已知信息中；有时他会忘记之前某局游戏结果，并把它从已知信息中删除。你的任务是：每当小 D 在已知信息中增加或删除一条信息时，根据小 D 记得的已知信息，帮助小 D 计算小 R 在 $ n $ 局游戏中总共获胜局数的期望是多少。 需要注意的是：如果小 D 忘了一局游戏的结果，之后又重新记起，两次记忆中的游戏结果不一定是相同的。你不需要关心小 D 的记忆是否与实际情况相符，你只需要根据他的记忆计算相应的答案。

第一行两个正整数 $ n， m $ 和一个字符串 $ \text{type} $。表示小 R 和小 B 一共玩了 $ n $ 局游戏，小 D 一共进行了 $ m $ 次修改已知信息的操作，该数据的类型为 $ \text{type} $。$ \text{type} $ 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入，其具体含义见「数据范围与提示」中的「限制与约定」。 接下来 $ n $ 行，第一行包含一个实数 $ p_1 $，表示第一局比赛小 R 获胜的概率是 $ p_1 $。第 $ i (1 < i \leq n) $ 行包含两个实数 $ pi_i, q_i $。表示在第 $ i − 1 $ 局游戏小 R 获胜的情况下，第 $ i $ 局游戏小 R 获胜的概率是 $ p_i $；$ q_i $ 表示在第 $ i − 1 $ 局游戏小 B 获胜的情况下，第 $ i $ 局游戏小 R 获胜的概率是 $ q_i $。 接下来 $ m $ 行，每行描述一个小 D 已知信息的变化，操作分为两类。 1. `add i c` 表示小 D 回忆起了第 $ i $ 局比赛的结果，并把它加入到已知信息中。若 $ c = 0 $ 表示第 $ i $ 局比赛小 B 获胜，若 $ c = 1 $ 表示第 $ i $ 局比赛小 R 获胜。数据保证 $ i, c $ 均为整数且 $ 1 \leq i \leq n, 0 \leq c \leq 1 $，如果这个操作不是第一个操作，保证在上一个操作结束后的已知信息中没有第 $ i $ 局比赛的结果。 2. `del i` 表示小 D 忘记了第 $ i $ 局比赛的结果，并把它从已知信息中删除。数据保证 $ i $ 是整数且 $ 1 \leq i \leq n $，保证在上一个操作结束后的已知信息中有第 $ i $ 局比赛的结果。

运用贝叶斯公式

第一问：

$$ \begin{aligned} p(x_2 = 1|x_1 = 1) &= 0.5 \ p(x_3 = 1|x_1 = 1) &= 0.5 \times 0.9 + 0.5 \times 0.8 = 0.85 \ E(x_1 +x_2 +x_3 |x_1 = 1) &= 0.5 + 0.85 + 1 = 2.35 \end{aligned} $$

第二问：

$$ \begin{aligned} p(x_2 = 1|x_1 = 1, x_3 = 0) &= \frac{p(x_3 =0|x_1=1,x_2=1)p(x_2 = 1|x_1 =1)}{p(x_3 =0|x_1 =1)} \approx 0.333 \ E(x_1 + x_2 + x_3|x_1 =1, x_3 = 0) &\approx 1.333 \end{aligned} $$

第三问：

对于

$$ p(x_2 = 1|x_3 = 0) = \frac{p(x_3 = 0|x_2 = 1)p(x_2 = 1)}{p(x_3 = 0)} $$

其中

$$ \begin{aligned} p(x_3 = 0|x_2 = 1) &= 0.1 \ p(x_2 = 1) &= 0.3 \times 0.5 + 0.7 \times 0.2 = 0.29 \ p(x_3 = 0) &= 0.29 \times 0.1 + 0.71 \times 0.2 = 0.171 \end{aligned} $$

所以

$$ p(x_2 = 1|x_3 = 0) = 0.1 \times 0.29/0.171 \approx 0.16959 $$

对于

$$ p(x_1 = 1|x_3 = 0) = \frac{p(x_3 =0|x_1=1)p(x_1=1)}{p(x_3 =0)} $$

其中

$$ \begin{aligned} p(x_3 = 0|x_1 = 1) &= 0.5 \times 0.1 + 0.5 \times 0.2 = 0.15 \ p(x_1 = 1) &= 0.3 \ p(x_3 = 0) &= 0.171 \end{aligned} $$

所以

$$ \begin{aligned} p(x_1 = 1|x_3 = 0) &= 0.15 \times 0.3/0.171 \approx 0.26316 \ E(x_1 + x_2 + x_3|x_3 = 0) &\approx 0.43275 \end{aligned} $$

#### 评分标准 如果你的答案与正确答案的绝对误差在 $ 10 ^ {−4} $ 以内，则被判定为正确。 如果你的所有答案均为正确，则得满分，否则得 0 分。 请注意输出格式：每行输出一个答案，答案只能为一个实数。每行的长度不得超过 50。错误输出格式会被判定为 0 分。 #### 限制与约定 对于 $ 100\% $ 的数据，$ 1 \leq n \leq 200000, 1 \leq m \leq 200000, 0 < pi, qi < 1 $。 对于 $ 100\% $ 的数据，输入保留最多四位小数。 本题共有 20 个数据点，每个数据点 5 分，每个测试点的具体约定如下表： | 测试点 | $ n $ | $ m $ | 数据类型 | |-|-|-|-| | 1 ~ 2 | $ \leq 10 $ | $ \leq 20 $ | A | | 3 ~ 4 | $ \leq 100 $ | $ \leq 100 $ | B | | 5 ~ 6 | $ \leq 1000 $ | $ \leq 5000 $ | A | | 7 ~ 9 | $ \leq 2000 $ | $ \leq 5000 $ | B | | 10 ~ 13 | $ \leq 10000 $ | $ \leq 200000 $ | B | | 14 ~ 15 | $ \leq 200000 $ | $ \leq 200000 $ | C | | 16 ~ 17 | $ \leq 200000 $ | $ \leq 200000 $ | D | | 18 ~ 20 | $ \leq 200000 $ | $ \leq 200000 $ | A | 数据类型的含义： * A：无限制 * B：$ \forall i > 1, |pi − qi| > 0.999 $ * C：同一时刻，小 D 最多只有 $ 1 $ 条已知信息 * D：同一时刻，小 D 最多只有 $ 5 $ 条已知信息 #### 小 R 教你学数学 你**可能**会用到以下公式 1. 条件概率的计算方法 我们记 $ p(A|B) $ 表示在已知事件 $ B $ 发生时事件 $ A $ 发生的概率，条件概率可以用以下公式计算： $$ p(A|B) = \frac{p(AB)}{p(B)} $$ 其中 $ p(AB) $ 表示事件 $ B $ 和事件 $ A $ 同时发生的概率，$ p(B) $ 表示事件 $ B $ 发生的概率。 2. 贝叶斯公式（bayes） 由条件概率的计算方法，我们容易得到贝叶斯公式： $$ p(A|B) = \frac{p(B|A)p(A)}{p(B)} $$ 3. 全概率公式 如果随机变量 $ x $ 有 $ k $ 个取值，分别为 $ x_1, x_2, \ldots, x_k $ 那么 $$ p(A) = \sum\limits_{i = 1} ^ k p(A|x = x_i) p(x = x_i) $$ #### 温馨提示 在本题中，如果你希望获得全部的分数，你可能需要考虑由于浮点数运算引入的误差。只使用加法和乘法运算不会引入太大的误差，但请谨慎使用减法和除法。 1. 两个大小相近的数相减可以引入非常大的相对误差。 2. 如果一个矩阵的行列式值非常小，那么求解该矩阵的逆可以带来相当大的误差。 当然，如果你的算法在数学上是正确的，但没有考虑浮点数运算的误差问题，可能仍然可以获得一部分的分数。