Training 2: Probability and Expectation

Problem A

Solved by Kilo_5723 && Weaver_zhu.

题意：给定一个无向联通图，每一条边有一个权值，从起点开始每次随机选一条边走，问走到终点时，走过的所有边权值异或和的期望值。

题解：对于边权的每一个二进制位分别求解，将每个点到终点路径异或和的期望值设为未知数，对每一个点及其所有出边列出方程，高斯消元求解即可。

Problem B

Solved by Kilo_5723 && Weaver_zhu.

题意：两个人在一个无向联通图的两点上，每个人在第 $i$ 个点上有 $p_i$ 的概率留在原点，有 $1-p_i$ 的概率从所有连边中随机选择一条出边去别的房间。每一个时刻，两人按如上规则随机移动，求两个人第一次选择去同一个房间时，这个房间是每个房间的概率。

题解：将两个人各自所在房间的二元组 $(a,b)$ 设为一个状态，将每个状态到达每个终态 $a=b$ 的概率设为未知量，对每一个二元组可能到达的二元组状态列出方程，高斯消元求解即可。

Problem C

Solved by Kilo_5723.

题意：你的生命值是 $p$，最大生命值是 $n$，每一次恢复一点生命值，随后有 $m$ 轮攻击，每轮攻击有 $frac{1}{p}$ 的概率对你造成 $1$ 点伤害。问你在被打死之前回复生命值的期望值。

题解：将每个生命值被打死之前回复生命值的期望值设为未知量，将每个血量可能到达的状态列出方程。我们发现，生命值为 $p$ 时最多可能达到 $p+1$，也就是说这个矩阵已经非常接近上三角矩阵，只要用每一行消下一行的第一个非零值就可以了。我们只需要求出一个未知量的值，那么用它下面的每一行的第一个非零值消这一行就可以了，整体复杂度是 $O(n^2)$ 的。

Problem D

Solved by Kilo_5723.

题意：$n$ 次操作，第 $i$ 次操作有 $p_i$ 的概率成功。最后的得分是每一段极长的连续成功操作串的长度的三次方和，求最后得分的期望值。

题解：对于任意一个从 $i$ 到 $j$ 的极长连续成功操作串，它对答案的贡献是 $(1-p_{i-1}) \times \prod_{k=i}^{j} p_k \times (1-p_{j+1}) \times (j-i+1)^3$。

拆分之后按 $\prod_{k=i}^{j} p_k$ 作为项求和，发现了在 $i \neq j$ 时，每一个 $\prod_{k=i}^{j} p_k$ 对答案的贡献是 $\prod_{k=i}^{j} p_k \times 6(j-i)$，$i=j$ 时贡献是 $p_i$。

将 $i \neq j$ 的情况进一步拆分，变成了 $6j \times \prod_{k=i}^{j} p_k - 6i \times \prod_{k=i}^{j} p_k$，这样我们就可以将所有同一起点的极长连续成功操作合并，同一终点的极长连续成功操作也合并，$O(n)$ 求出总贡献。

Problem E

Solved by Kilo_5723.

题意：给定一棵有根树，每次随机取走一个节点及其子树，问期望下要取多少次才能将根节点取走。

题解：定义每次取走的节点为被直接取走的，其子树的节点为被被动取走的，我们发现答案只和被成功取走的节点个数有关。

考虑每一个节点被直接取走的概率：对于一个节点，会影响其被直接取走的概率的只有其到根节点链上的节点。其他节点就算被取走也不会影响这个节点被取走的概率，而这条链上该节点的父节点只要有一个被取走都会导致该节点被被动取走。

因此，每个节点被直接取走的概率等于其先于其所有父节点被去走的概率，是 $\frac{1}{depth}$。对 $\frac{1}{depth}$ 求和即可。

Problem F

Solved by Kilo_5723.

题意：一个周期有 $n$ 天，有 $t$ 个系列比赛，每个系列比赛要占用可能不连续的 $m$ 天，但每个系列比赛第一天和最后一天的时间差不会超过 $10000$。定义快乐度为每一天的比赛数量的平方和，求期望的快乐度。

题解：维护每一天有 $0$ ~ $t$ 场比赛的概率即可，到了第 $10000$ 天之后这个概率就不会变了，直接乘就行。

注意维护方式，维护的时间要计入大整数的费时，小心 TLE，尽量少用乘除法。

Problem G

Solved by Kilo_5723.

题意：$r$ 轮操作，每一轮扫一遍 $n$ 个卡牌，每个卡牌有 $p_i$ 的概率被触发，触发造成 $d_i$ 伤害。已经触发的卡牌不会被触发，每一轮第一次有卡牌被触发就停止，问造成伤害的期望值。

题解：看似每一轮都要进行完才能进行下一轮，但我们可以让 $r$ 轮操作同步进行。

从左到右处理每一张卡牌，我们发现第一张卡牌有 $(1-p_i)^n$ 的概率不被触发，此时相当于第二张卡牌开始执行 $r$ 轮操作的伤害期望值。第一张卡牌如果被触发，相当于从第二张卡牌执行 $r-1$ 轮操作的伤害期望值 $+d_i$。

对这种状态转移推广，设 $dp[i][j]$ 代表从第 $i$ 张卡牌开始执行 $j$ 轮操作的伤害期望值，则 $dp[i][j]=(1-p_i)^j \times dp[i+1][j]+(1-(1-p_i)^j) \times (dp[i+1][j-1]+d_i)$，$dp[1][r]$ 就是答案。

Problem H

Solved by Kilo_5723.

题意：一个点从原点开始，有 $p_1,p_2,p_3,p_4$ 的概率项四个方向移动，问期望多少次移动之后会走出以原点为圆心，半径为 $R$ 的圆。

题解：将每一个点的期望移动次数作为未知量，以每个点向四个方向移动的行为建立方程。未知数的总量虽然很大，但是如果采取恰当的消元顺序，可以保证每一时刻每个方程的未知量的个数是 $O(R)$ 的。

采取按照点到原点距离从大到小的顺序消元，用恰当的方式储存每个方程即可。注意每次消元都要用未知数的数量最小的方程消除其他方程。