题集

发现自己期望太差了，写写题。

大部分题目来自这个题单

绿豆蛙的归宿

给出一张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$ ，终点为 $n$ ，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。从起点出发，走向终点。到达每一个顶点时，如果该节点有 $k$ 条出边，可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$ 。求出从起点走到终点的所经过的路径总长度期望。

数据范围： $n\le 10^5, m\le 2\times 10^5$ 。

典题。由于是有向无环图，我们可以进行一个拓扑 dp。我们设 $f_u$ 为 $u$ 到终点的期望步数，那么我们枚举走那条出边可以得到转移方程：

f_u=\frac{1}{dout_u} \sum\limits_{(u, v)\in E} f_v

初始状态为： $f_{end}=0$ 。

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

单选错位

试卷上共有 $n$ 道单选题，第 $i$ 道单选题有 $a_i$ 个选项，这 $a_i$ 个选项编号是 $1,2,3,\ldots,a_i$ ，每个选项成为正确答案的概率都是相等的。将第 $i$ 个位置的正确答案填到第 $i+1$ 个位置（第 $n$ 个位置的答案填到第 $1$ 个位置），求期望答对多少题。

数据范围： $n\le 10^7$ 。

我们进行一个分类讨论。

当 $a_i >a_{i+1}$ 时，我们需要先确保第 $i$ 题的答案不在第 $a_{i+1}+1\sim a_i$ 这段区间，然后再保证这两道题的答案相同，因此第 $i+1$ 题答对的概率是： $\frac{a_{i+1}}{a_{i}}\times \frac{1}{a_i^2}\times a_i=\frac{1}{a_i}$ 。

同理我们可以得到当 $a_i\le a_{i+1}$ 时第 $i+1$ 题答对的概率是 $\frac{1}{a_{i+1}}$ 。因此第 $i+1$ 题答对的概率为 $\frac{1}{\max(a_i,a_{i+1})}$ 。

最后我们把每道题答对的概率相加即为答案。时间复杂度 $O(n)$ 。

Vasya and Magic Matrix

一个 $n$ 行 $m$ 列的矩阵,每个位置有权值 $a_{i,j}$ 。给定一个出发点,每次可以等概率的移动到一个权值小于当前点权值的点（不能移动就停止），同时得分加上两个点之间欧几里得距离的平方，问得分的期望。

数据范围： $n, m\le 1000$ 。

我们设 $f_{i, j}$ 为 $(i, j)$ 这个位置一直移动到不能移动为止的期望步数。我们可以从小到大加入权值，这样就不会受其他权值的影响。我们设 $S$ 为已经加入的点的点集，我们在考虑完一批值相同的点之后才会将它们加入 $S$ 。

我们来考虑如何转移 $f_{i, j}$ 。转移其实很简单，就是它到场上每个点的距离和。因此转移为

\begin{aligned} f_{x, y}&=\sum \limits_{(a, b)\in S} \left((x-a)^2+(y-b)^2+f_{a, b} \right)\\ &=\sum \limits_{(a, b)\in S} (x-a)^2+\sum \limits_{(a, b)\in S}(y-b)^2+\sum \limits_{(a, b)\in S} f_{a, b} \end{aligned}

后面 $f$ 的和可以直接维护，而前面的平方可以拆开，这样就只用维护 $x$ 的和， $x$ 的平方和以及 $y$ 的这些信息了。

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

OSU!

一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$ ，失败对应 $0$ ， $n$ 次操作对应为 $1$ 个长度为 $n$ 的 01 串。在这个串中连续的 $X$ 个 $1$ 可以贡献 $X^3$ 的分数，这 $x$ 个 $1$ 不能被其他连续的 $1$ 所包含（也就是极长的一串 $1$ ）。给出每个操作的成功率 $p_i$ ，求出期望分数。

数据范围： $n \leq 1 \times 10 ^ 5$ 。

根据期望的性质： $E(x+y)=E(x)+E(y)$ ，因此我们可以得到： $E((x+1)^3)=E(x^3+3x^2+3x+1)=E(x^3)+3E(x^2)+3E(x)+1$ 。因此我们设 $a_i$ 为最后以 $i$ 为末尾的连续 $1$ 段长度的期望， $b_i$ 为为最后以 $i$ 为末尾的连续 $1$ 段长度平方的期望， $f_i$ 为前 $i$ 个操作的期望得分，那么我们就能得到方程：

a_i=(a_{i-1}+1)\times p_i

b_i=(b_{i-1}+2a_{i-1}+1)\times p_i

我们可以发现 $x+1$ 和 $x$ 的答案只相差了 $3E(x^2)+3E(x)+1$ ，因此得到

f_i=f_{i-1}+(3\times b_{i-1}+3\times a_{i-1}+1)\times p_i

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

Fish

有 $n$ 条鱼，每天有一对鱼相遇，彼此相遇的概率是一样的。如果两条标号为 $i$ 和 $j$ 的鱼见面，第一只吃第二只的概率为 $a_{i,j}$ ，第二只会吃第一只的概率为 $a_{j,i}=1-a_{i,j}$ 。该过程进行到湖里只剩下一条鱼。请你算出每只鱼最后存活在湖里的可能性。

数据范围： $n\le 18$ 。

简单状压。我们可以设 $f_{s}$ 为 $s$ 这些鱼都存活下来的概率。转移时我们就可以枚举哪两只鱼相遇，同时看谁吃掉谁。假设 $i$ 吃掉 $j$ 之后的状态为 $T$ ， $s$ 状态中还剩下 $x$ 条鱼，则转移为：

f_T\leftarrow \frac{f_s \times a_{i, j}}{x\times (x-1)}

这里分母没有除以二的原因是作者直接 $i, j$ 都是全部枚举的，每个会计算两遍就达到了分母除以二的效果。

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

换教室

有 $n$ 节课程， $v$ 个教室， $e$ 条道路，每节课程原先是在第 $c_i$ 个教室上课，可以申请换到第 $d_i$ 个教室上课。每节课结束后都会从当前教室选择耗费体力最少的道路到下一个教室上课。

现在有 $m$ 次申请换教室的机会（可以不用完），对于第 $i$ 节课程，申请通过的概率为 $p_i$ ，每节课程只能申请一次。问怎么申请才能让他移动消耗的体力值的期望最小，求出最小值。

数据范围： $n,m\le 2000, v\le 300, e\le 90000$ 。

我们先跑一遍 floyd，求出两点之间的最短路，方便后面的 dp。

我们设 $f[i][j][0/1]$ 为当前考虑到第 $i$ 节课程，用了 $j$ 次申请机会，当前这节课程是否申请的期望。分析一下就能得出以下转移方程：

\begin{aligned} f[i][j][0] &= \min(f[i][j][0], f[i - 1][j][0] + dist[c[i - 1]][c[i]]);\\ f[i][j][0] &= \min(f[i][j][0], f[i - 1][j][1] + dist[d[i - 1]][c[i]] * p[i - 1] + dist[c[i - 1]][c[i]] * (1 - p[i - 1])); \end{aligned}

当前申请的转移方程也同理可以推出，这里就不再写出。

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

Expected diameter of a tree

给一片森林， $q$ 次询问，每个询问两个点，问在这两个点所在的树中各随机选取两个点，将这两个点连接起来组成的新树，它的直径的期望值是多少。

数据范围： $n, q\le 10^5$

我们可以首先求出所有连接情况直径的和，最后再除以 $siz_x\times siz_y$ 即可。

我们先设 $ans_x$ 为 $x$ 这棵树的直径， $mx_u$ 为 $u$ 在树中最远能走多远。我们最终的直径一定是这样一个形式： $\max (ans_x, ans_y, mx_x+mx_y+1)$ 。我们枚举一棵树中的点 $x$ ，考虑另一棵树中有多少 $y$ 能让 $mx_x+mx_y+1$ 成为最终的答案。

我们假设 $dx=\max(ans_x, ans_y)$ ，那么我们移项可得： $mx_y\ge dx - mx_x-1$ 。我们只需要找出所有满足这个条件的 $y$ 的数量以及它们的 $mx$ 之和。这个东西可以直接前缀和搞。

最后我们考虑时间复杂度，我们可以枚举点的时候枚举小树的点。同时我们可以进行一个记忆化。可以证明这样的时间复杂度为 $O(n\sqrt n)$ 。

亚瑟王

玩家有一套卡牌，共 $n$ 张。游戏时，玩家将 $n$ 张卡牌排列成某种顺序，排列后将卡牌按从前往后依次编号为 $1 - n$ 。本题中，顺序已经确定，即为输入的顺序。每张卡牌都有一个技能。第 $i$ 张卡牌的技能发动概率为 $p_i$ ，如果成功发动，则会对敌方造成 $d_i$ 点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。基于现实因素以及小 K 非洲血统的考虑， $p_i$ 不会为 $0$ ，也不会为 $1$ ，即 $0 < p_i < 1$ 。一局游戏一共有 $r$ 轮。在每一轮中，系统将从第一张卡牌开始，按照顺序依次考虑每张卡牌。在一轮中，对于依次考虑的每一张卡牌：

如果这张卡牌在这一局游戏中已经发动过技能，则如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）；否则（是最后一张），结束这一轮游戏。

2. 否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 $i$ 张，将其以 $p_i$ 的概率发动技能。如果技能发动，则对敌方造成 $d_i$ 点伤害，并结束这一轮。如果这张卡牌已经是最后一张（即 $i$ 等于 $n$ ），则结束这一轮；否则，考虑下一张卡牌。

请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

数据范围： $1 \leq T \leq 444, 1 \leq n \leq 220, 0 \leq r \leq 132, 0 < p_i < 1, 0 \leq d_i \leq 1000$ 。

我们可以对每个卡牌算出它发动的概率 $D_i$ ，那么最终的伤害的期望就是每个卡牌造成的伤害再乘上它发动的概率之和。

我们现在就要求出所有卡牌的概率。我们可以发现第一张卡牌不发动的概率为 $(1-p_1)^{r}$ ，发动的概率为 $1-(1-p_1)^r$ 。而对于后面的卡牌，我们发现如果在一轮中，它前面的卡牌发动过，那么它就没法发动。因此我们设 $f_{i, j}$ 为在这 $r$ 轮中，前 $i$ 张卡牌，发动 $j$ 张的概率。转移就看是否发动当前这一张即可。

发动这一张，那么转移为：

f_{i, j}\leftarrow f_{i-1, j-1}\times (1-(1-p_j)^{r-j+1})

不发动这一张，转移为：

f_{i, j}\leftarrow f_{i-1, j}\times (1-p_j)^{r-j}

最终我们求的 $D_i$ 就是 $\sum \limits_{j=0}^{\min(i-1, r)}f_{i-1, j}\times (1-(1-p_i)^{r-j})$ 。

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

游走

给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$ ，边从 $1$ 编号到 $m$ 。在该图上进行随机游走，初始时在 $1$ 号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这 $m$ 条边进行编号，使得获得的总分的期望值最小。

数据范围： $n\le 500, m\le 125000$ 。

我们发现边的数量太多不好求每条边的期望，但是如果我们求出了每个点期望经过的次数 $f_u$ ，那么一条边 $(x, y)$ 期望经过的次数就是 $\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$ 。

现在只需要求出 $f_u$ 。我们可以把转移的式子写出来：

f_u=\sum \limits_{(u, v)\in E}\frac{f_v}{deg_v} +[u=1]

高斯消元即可。时间复杂度 $O(n^3)$ 。

分手是祝愿

B 君在玩一个游戏，这个游戏由 $n$ 个灯和 $n$ 个开关组成，给定这 $n$ 个灯的初始状态，下标为从 $1$ 到 $n$ 的正整数。

每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$ ）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。

这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 $k$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 $k$ 步）操作这些开关。

B 君想知道按照这个策略（也就是先随机操作，最后小于等于 $k$ 步，使用操作次数最小的操作方法）的操作次数的期望。

数据范围： $n\le 100000$ 。

首先我们考虑 $k=n$ 的测试点，我们可以发现高位的灯不可能由低位的灯给按灭，而且我们为了按灭所有灯所做的所有操作都不能省略。因此我们有一个方案：从高位往低位按，模拟即可。这样我们就能算出最小操作次数 $x$ 。

我们再考虑随机操作。我们可以假设当前局面还需要按 $i$ 次才能全灭（我们设 $f_i$ 为从按 $i$ 次全灭走到按 $i-1$ 次全灭的状态的期望步数），由于我们操作的顺序不会影响结果，因此我们在这个局面随机按一次有 $\frac{i}{n}$ 的概率走到 $f_{i-1}$ ，有 $\frac{n-i}{n}$ 的概率走到 $f_{i+1}$ 。因此转移方程为：

f_i=\frac{i}{n}+\frac{n-i}{n}(f_{i+1}+f_i+1)

可以得到 $f_i=\frac{(n-i)f_{i+1}+n}{i}$ 。初始状态 $f_n=1$ ，最终答案为 $k+\sum \limits_{i=k+1}^x f_i$ 。

时间复杂度 $O(n\sqrt n)$ 或者可以做到 $O(n\log n)$ 。

仓鼠找sugar II

给定一棵树，随机选取两个点 $a, b$ ，从 $a$ 开始随机游走（走每个出边的概率相同），期望走多少步到 $b$ 。

数据范围： $n\le 10^5$ 。

树上随机游走模板题。

我们先分析边有边权的情况。设 $f_u$ 为 $u$ 期望走多远走到它的父亲节点。

f_u=\frac{w_{u, fa}+\sum\limits_{v\in son_u} (w_{u, v}+f_v+f_v)}{deg_u}

分母是向每条出边走的概率都相同，分子第一项是直接向父亲走，第二项是先向儿子走，再从儿子走回来再走向父亲的距离。我们继续推式子。

\begin{aligned} f_u&=\frac{w_{u, fa}+\sum\limits_{v\in son_u} (w_{u, v}+f_v+f_v)}{deg_u}\\ &=\frac{w_{u, fa}+\sum\limits_{v\in son_u} (w_{u, v}+f_v)+(deg_u-1)f_v}{deg_u}\\ &=w_{u, fa}+\sum\limits_{v\in son_u} (w_{u, v}+f_v)\\ &=\sum \limits_{(u, v)\in E} w_{u, v}+\sum \limits_{v\in son_u}f_v \end{aligned}

而在本题中就是 $w=1$ 的情况，这时式子变为：

f_u=deg_u+\sum \limits_{v\in son_u}f_v

也就是子树所有点的度数和，这个值就等于 $2\times siz_u-1$ 。

在本题中我们可以固定一个根，让每个节点往上走，这时每条边的贡献就是 $(2\times siz_u-1)\times siz_u$ 。最后换根 dp 一下就可以。

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

Game on Tree

给定一棵有根树，结点编号从 $1$ 到 $n$ 。根结点为 $1$ 号结点。

对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。

要求求出删除所有结点的期望操作次数。

数据范围： $n\le 10^5$ 。

设 $f_i$ 为 $i$ 号点被选中的次数，那么我们要求的答案为 $E(\sum f_u)=\sum E(f_u)$ ，也就是每个点被选中的概率之和。

我们考虑一个点如何才能被选中，也就是它在它任意一个祖先选中之前被选中，而它有 $dep_u-1$ 个祖先，因此它排在所有祖先之前的概率是 $\frac{1}{dep_u}$ 。因此答案为 $\sum \frac{1}{dep_u}$ 。

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

重建

给定一张 $n$ 个点的完全图，给出每条边的出现概率，求出最终成为一颗生成树的概率。

数据范围： $n\le 50$ 。

矩阵树定理其实求的是这么个玩意：

\sum_{T\in Tree}\prod_{e\in T} w_e

但是这题我们要求的东西是这个玩意：

\sum_{T\in Tree}\prod_{e\in T} p_e\prod_{e\not \in T}(1-p_e)

我们可以把后面的式子化开：

\begin{aligned} \sum_{T\in Tree}\prod_{e\in T} p_e\prod_{e\not \in T}(1-p_e)&=\sum_{T\in Tree}\prod_{e\in T} p_e\frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}\\ &=\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T}\frac{p_e}{1-p_e} \end{aligned}

我们可以把每条边的边权弄成 $\frac{p_e}{1-p_e}$ ，然后矩阵树定理即可。

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

随机树

一棵含 $n$ 个叶结点的二叉树可以通过如下方式生成：初始时只有根结点。首先，将根结点展开（本题中的展开是指给一个叶结点添上左、右两个子结点）；然后，等概率地随机将两个叶结点中的一个展开，即生成以下两棵树之一:之后，每次在当前二叉树的所有叶结点中，等概率地随机选择一个，将其展开。

不断地重复这一操作，直至产生 $n$ 个叶结点为止。对于这样随机生成的一颗 $n$ 个叶子节点的二叉树，求出叶节点的平均深度的数学期望、树最大深度的数学期望。

数据范围： $n\le 100$ 。

第一问很好解决。我们设 $f_i$ 为 $i$ 个叶子节点的树的叶子的平均深度，展开一个叶子节点，那么深度总和平均下来会增加 $f_{i-1}+2$ 。因此转移方程为：

f_i=\frac{(i-1)f_{i-1}+f_{i-1}+2}{i}=f_{i-1}+\frac{2}{i}

而对于第二问，有一个公式： $E(x)=\sum P(i\le x)$ 。也就是随机变量 $x$ 的期望就等于对于所有 $i$ ， $i\le x$ 的概率之和。

这样我们可以设 $g_{i, j}$ 为有 $i$ 个叶子，树深度大于等于 $j$ 的概率。转移时我们枚举一颗子树内有多少叶子，然后令它的叶子节点深度大于等于 $j-1$ 即可。同时这样我们会计算两遍两棵子树深度都大于 $j-1$ 的情况，减去即可。

因此转移为：

g_{i, j}=\frac{1}{i-1}\sum\limits_{k=1}^{i-1} (f_{k, j-1}+f_{i-k, j-1}-f_{k, j-1}\times f_{i-k, j-1})

然后根据我们上面的公式，我们就可以得到最终的答案： $\sum \limits_{i=1}^{n-1}f_{n, i}$ 。

补充：关于 $g_{i, j}$ 的转移过程中，前面除去 $i-1$ 的原因：

我们设 $P_k$ 为一颗左儿子有 $k$ 个叶子，右儿子有 $i-k$ 个叶子的树，深度大于 $j$ 的概率，根据上面的分析我们可以得到 $P_k=(f_{k, j-1}+f_{i-k, j-1}-f_{k, j-1}\times f_{i-k, j-1})$ 。

我们再设 $P_k'$ 为生成一颗左儿子有 $k$ 个叶子，右儿子有 $i-k$ 个叶子的树的概率，那么我们上面求的 $g_{i, j}$ 即为 $\sum\limits_{k=1}^{i-1}P_k'P_k$ 。因此我们要证明的就是 $P_k'=\frac{1}{i-1}$ 。

我们考虑把生成的这个过程用 $L$ （分裂左儿子）和 $R$ （分裂右儿子）来表示，那么最终生成这棵树的序列即为一个长度为 $i-2$ ，且有 $k-1$ 个 $L$ ， $i-k-1$ 个 $R$ 的序列（根节点一开始被分裂）。我们就能知道这个操作序列的排列有 $\frac{(i-2)!}{(k-1)!(i-k-1)!}$ 种。

而对于 $L$ 和 $R$ 内部的排布，当我们有 $1$ 个 $L$ 时我们分裂 $L$ 只有 $1$ 种选择，两个 $L$ 就能有两种选择，以此类推 $L$ 内部的排列就有 $(i-1)!$ 种。 $R$ 同理有 $(i-k-1)!$ 种。我们用乘法原理把这些步骤乘起来，就能得到一共有 $(i-2)!$ 种左儿子有 $k$ 个的树，也就和 $k$ 无关了。因此这样做才是正确的。

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

游戏

有 $n$ 个办公室，编号为 $l\sim l+n-1$ ，当检查完编号为 $i$ 的办公室后这个办公室的人会通知所有编号为 $i$ 的倍数的办公室的人认真工作。

对于一个检查办公室的顺序 $p$ ，当检查完 $p_1, p_2\cdots p_x$ 这些办公室后所有办公室都开始认真工作，那么就把 $x$ 称为 $p$ 的检查时间。

求出对于所有顺序 $p$ ，它们的检查时间之和。

数据范围： $l, n\le 10^7$ 。

我们发现后面的办公室是没法更新前面的办公室的。因此我们先从前往后扫一遍，用类似埃筛的思想筛出除了自己之外无法被别的办公室更新的点的数量 $x$ ，我们称之为有效点。

显然，一个顺序的检查时间就等于它最后出现的有效点的位置。我们可以算出有多少个无效点会在最后一个有效点之后：

$k$ 个有效点会将序列分为 $k+1$ 段，那么就期望有 $\frac{n-k}{k+1}$ 个点会在最后一个有效点之后。那么最后一个有效点的位置期望就是 $n-\frac{n-k}{k+1}=\frac{nk+n-n+k}{k+1}=\frac{k(n+1)}{k+1}$ 。

而我们算出的是期望值，我们只需要乘一下有多少个顺序就可以得到答案。因此最终答案为 $\frac{k}{k+1}(n+1)!$ 。

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

yyf hates dagequ

给你一些卡牌的技能，技能分为 $2$ 种类型：

加分，每连击 $c$ 次有 $p$ 的概率加 $s$ 分
改判，每连击 $c$ 次有 $p$ 的概率触发强判定效果，持续 $t$ 个节奏图标（设连击数为 $c$ 的倍数时为第 $i$ 个节奏图标，则强判定效果在第 $[i+1,i+t]$ 个节奏图标被触发）

这些技能在连击数为 $c$ 的倍数且连击数不为 $0$ 时有概率触发，多个技能可以同时触发。其中，加分技能有 $\mathrm{score}$ 个，改判技能有 $\mathrm{judge}$ 个。

再给你 $n$ 个节奏图标（crimson000 是按给出的顺序击打的）crimson000 击打的原始（相对于“强判定效果”修正后）结果，分为 $2$ ， $1$ ， $0$ 三种。在”强判定效果”的持续期间内所有的击打结果 $1$ 会视作击打结果 $2$ ，击打结果 $0$ 仍视作击打结果 $0$ ，击打结果 $2$ 仍视作击打结果 $2$ 。下文中的“击打结果”若无说明均指修正后的击打结果。

“连击数”的定义为到目前为止连续的击打结果为 $2$ 的次数（若这次的击打结果为 $2$ 则这次击打也算入当前的连击数，否则当前的连击数为 $0$ ）。

多个“强判定效果”可以重叠，但持续时间不会叠加（设当前“强判定效果”剩余时间为 $t_1$ ，此时同时触发两个“强判定效果”，持续时间分别为 $t_2$ 和 $t_3$ ，则下一次击打时的“强判定效果”剩余时间为 $\max(t_1-1,t_2,t_3)$ ）。

一次击打的得分为这次的击打结果乘以当前的连击数加一。即：设当前的击打结果为 $x$ ，当前的连击数为 $\mathrm{combo}$ ，则这次击打的得分为 $\mathrm{x*(combo+1)}$ 。最终得分为每次（共 $n$ 次）击打的得分之和加上加分技能的加分之和

请求出 crimson000 这次被歌暴打的期望得分。

数据范围： $5 \le n \le 1000$ ， $0 \le \mathrm{score} \le 1000$ ， $0 \le \mathrm{judge} \le 1000$ ， $1 \le c \le 5$ ， $0.01 \le p \le 0.99$ ， $1 \le s \le 10$ ， $1 \le t \le 5$ 。

我们可以注意到改判持续的时间很短，因此我们可以直接把它记录到状态里面。

因此我们设 $f[i, j, k]$ 为当前该打第 $i$ 个音符，已经有了 $j$ 个 combo，改判还有 $k$ 个音符结束的期望得分。我们注意到加分的操作只和 combo 数有关，因此我们可以预处理出一个数组 $sc[i]$ ，为当 combo 数为 $i$ 时期望加的分数。

转移时我们就看当前 $a_i$ 和 $k$ ，当 $a_i=0$ 或 $k=0, a_i=1$ 的情况很好处理，而对于其他情况，我们就要考虑当前是否有可能触发改判操作。

首先一个直观的想法就是枚举集合，看触发哪些改判操作。这样转移的复杂度会达到 $O(2^{\mathrm{judge}})$ 。我们考虑优化。

我们可以注意到当一个 $t$ 更大的改判执行时， $t$ 小的改判执不执行已经不重要了，因此我们可以先对改判操作排序，然后预处理出当某个改判作为 $t$ 最大的改判执行的概率。而我们在转移的时候我们就可以枚举那个改判持续的时间是多少，这样只用枚举 $t$ 个数就可以完成转移。

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

概率充电器

概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时，每条导线 $(u, v)$ 是否可以导电以概率 $p_{u, v}$ 决定，每一个充电元件自身是否直接进行充电也由概率 $q_u$ 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。求出进入充电状态的元件个数的期望。

数据范围： $n\le 10^5$ 。

我们设 $f_u$ 为 $u$ 充上电的概率，那么答案就是 $\sum_{i=1}^n f_i$ 。

我们考虑一个点充上电的概率来自哪里：

它自己充上电的 $q_i$ 。
它子树中的电传到他这里。
电从它父亲传到它。

我们可以先考虑第二种，然后再一次 dfs 来统计第三种。

下文中设 $u$ 为父亲， $v$ 为儿子。

我们考虑第二种的转移。我们设 $P(A)$ 为通过其他方式 $u$ 充上电的概率（也就是当前的 $f_u$ ，我们设为 $f_u'$ ）， $P(B)$ 为 $v$ 传给它电的概率。那么我们根据概率的公式，我们可以得到：

\begin{aligned} f_u&=P(A)+P(B)-P(AB)\\ &=f_u'+f_v\times p_{u, v}-f_u'\times f_v\times p_{u, v} \end{aligned}

这样就完成了对子树的统计，而对于父亲来的电，我们先把这颗子树对父亲的贡献去掉。

我们假设更新完了 $u$ 通过上面三种情况来电的概率，那么我们设 $P(A)$ 为 $u$ 通过除去 $v$ 子树以外的来电的概率， $P(B)$ 为 $v$ 子树给 $u$ 供上电的概率，那么可以得到等式：

f_u=P(B)+P(A)-P(AB)

其中 $P(B)=f_v\times p_{u, v}$ ，那么我们就可以得到 $P(A)=\frac{f_u-P(B)}{1-P(B)}$ 。

我们再考虑更新 $f_v$ 。我们设 $f_v'$ 为更新前的 $f_v$ ，那么还是根据那个公式，我们可以得到：

f_v=f_v'+P(A)\times p_{u, v}-f_v\times P(A)\times p_{u, v}

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

Intergalaxy Trips

给定一张 $n$ 个点的有向完全图， $i \to j$ 的边每天出现的概率均为 $p_{i,j}$ ，若 $i = j$ ，有 $p_{i,j} = 1$ 。每天可以选择一条存在的出边走过去或停留在原地不动。求最优策略下从 $1$ 到 $n$ 的期望天数。

数据范围： $n \le 10^3$ 。

我们设 $f_u$ 为 $u\to n$ 的期望步数，那么显然 $f_n=0$ 。我们考虑转移。

我们可以发现，如果有一条 $(u, v)$ 的边出现了，那么当 $f_v>f_u$ 时，我们一定不会去走 $(u, v)$ 这条边。因为我们这样走的期望步数还会增加，还不如直接走个自环。而当如果所有 $f_{v'}<f_v$ 的 $(u, v')$ 这条边不存在时，我们才会走 $(u, v)$ 这条边。

因此我们可以初步写出一个方程：

f_u=\sum_{v}^{f_v<f_u}p_{u, v}f_v\prod _{k}^{f_k<f_v}(1-p_{u, k})+f_u\prod _{v}^{f_v<f_u}(1-p_{u,v})+1

移项得到：

f_u=\frac{\sum_{v}^{f_v<f_u}p_{u, v}f_v\prod _{k}^{f_k<f_v}(1-p_{u, k})+1}{1-\prod_{v}^{f_v<f_u}(1-p_{u, v})}

这就是我们要的转移式子。

我们再考虑如何更新。我们可以发现一个点如果考虑的点越多，它的 $f$ 是不增的，同时不可能会用更大的 $f$ 来更新它。换句话说就是如果一个点的 $f$ 是全局最小，那么就没有别的点会更新它，也就是它的 $f$ 值已经固定了。我们就可以用类似 dijkstra 的思路来更新了。

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

Rainbow Balls

有一袋球，有 $n$ 种颜色，其中第 $i$ 个颜色的球有 $a_i$ 个。

当袋子里至少有两个不同颜色的球时，执行以下步骤:

一个接一个的按照顺序随机取出两个的球，这些球的颜色可能是一样的。
把第二个球涂成第一个球的颜色，然后把两个球放回袋子里。

所有这些动作只需要一秒钟。输出无法操作时候的期望时间

数据范围： $n\le 2500,1\le a_i \le 10^5$ 。

设 $s=\sum a_i$ 。我们先设一个目标颜色 $x$ ，也就是我们最终要的颜色全部相同的颜色。我们再设 $f_i$ 为当前有 $i$ 个目标颜色，到最终全部是 $x$ 的期望时间。最终答案就是 $\sum f_{a_i}$

我们考虑转移。我们先设 $p$ 为从盒子中选出两个球，其中第一个是 $x$ ，第二个不是 $x$ 的概率，显然 $p=\frac{i(s-i)}{s(s-1)}$ 。那么我们转移就能写出来为：

f_i=(f_{i+1}+f_{i-1})p+(1-2p)f_i+\color{red}1

但是我们发现这样转移是错误的，因为我们转移时不能保证它不到达 $f_0$ 这个情况，这时 $f_0$ 不存在。因此我们转移时加上的应该是它能不经过 $f_0$ 走到 $f_s$ 的概率，我们记作 $v$ 。

如何求出 $v$ 呢，我们可以设 $g_i$ 为有 $i$ 个 $x$ 时 $x$ 留到最后的概率，那么我们可以写出转移：

g_i=g_{i-1}p+g_{i+1}p+(1-2p)g_i

我们可以得出这么一个结论： $g_{i+1}-g_{i}=g_i-g_{i-1}$ 。而初始状态为： $g_0=0, g_s=1$ 。那么我们就可以得到 $v=g_i=\frac{i}{s}$ 。

我们带回原式即可得到：

\begin{aligned} f_i&=(f_{i+1}+f_{i-1})p+(1-2p)f_i+\frac{i}{s}\\ 2pf_i&=(f_{i+1}+f_{i-1})p+\frac{i}{s}\\ 2f_i&=f_{i+1}+f_{i-1}+\frac{i}{s\times \frac{i(s-i)}{s(s-1)}}\\ 2f_i&=f_{i+1}+f_{i-1}+\frac{s-1}{s-i}\\ f_{i+1}&=2f_i-f_{i-1}-\frac{s-1}{s-i} \end{aligned}

我们就得到了递推的公式，但是现在 $f_1$ 和 $f_2$ 未知，无法计算。我们考虑求出这俩玩意。

首先当 $i=0$ 时 $f_0$ 不存在，因此 $f_2=2f_1-1$ 。我们再设 $g_i=f_{i+1}-f_i$ ，根据上面我们推导的式子 $f_{i+1}-f_{i}=f_i-f_{i-1}-\frac{s-1}{s-i}$ ，我们就能得到 $g_i=g_{i-1}-\frac{s-1}{s-i}$ ，特殊情况即为 $g_0=f_1$ ，因此 $g_i=f_1-\sum\limits_{j=1}^i\frac{s-1}{s-j}$ 。

我们又知道 $f_s=0$ ，同时 $f_s=f_1+\sum\limits_{i=1}^{n-1}g_i$ 。我们再推下式子：

\begin{aligned} 0&=f_1+\sum_{i=1}^{s-1}g_i\\ &=f_1+\sum_{i=1}^{s-1}(f_1-\sum_{j=1}^i \frac{s-1}{s-j})\\ &=sf_1-\sum\limits_{i=1}^{s-1}\sum_{j=1}^i\frac{s-1}{s-j}\\ &=sf_1-\sum_{j=1}^{s-1}\sum_{i=j}^{s-1}\frac{s-1}{s-j}\\ &=sf_1-\sum_{j=1}^{s-1}\frac{s-1}{s-j}(s-j)\\ &=sf_1-(s-1)^2 \end{aligned}

解得 $f_1=\frac{(s-1)^2}{s}$ 。再根据 $f_2=2f_1-1$ 就可以递推了。

时间复杂度 $O(\max(a_i))$ 。

Student’s Camp

有一个 $(n+2) \times m$ 的网格。除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率消失。求 $k$ 天后，网格始终保持连通的概率。

数据范围： $n,m \le 1.5 \times 10^3$ ， $k \le 10^5$ 。

我们设 $D(i)$ 为这 $k$ 天从一边消失恰好 $i$ 个格子的概率，显然 $D(i)=\dbinom{k}{i}p^i(1-p)^{k-i}$ 。我们再设 $P(l, r)$ 为 $k$ 天后一行网格中恰好 $[l, r]$ 这段区间保持连通的概率，那么由于左右两边是相互独立的，就有 $P(l,r)=D(l-1)D(m-r)$ 。

我们设 $f[i, l, r]$ 为第 $i$ 行 $[l,r]$ 没有消失，且和前 $i-1$ 行保持连通的概率，那么比较显然的转移是进行一个区间 dp，上一行的区间只要和这一行有交即可。但是这样转移的复杂度是 $O(nm^4)$ 的，我们考虑用容斥优化一下。

我们发现要减去的情况只有 $r'<l$ 和 $r<l'$ 这两种情况，于是我们就可以写出转移：

f[i, l, r]=P(l, r)\left(\sum\limits_{l'\le r'}f[i-1,l',r']-\sum\limits_{r'<l}f[i-1, l', r']-\sum\limits_{l'>r}f[i-1, l', r'] \right)

我们把这三个 $\sum$ 都表示出来：

F_i=\sum\limits_{l'\le r'}f[i,l',r']

L[i, x]=\sum\limits_{l\le r <x} f[i, l, r]

R[i, x]=\sum \limits_{x<l\le r} f[i, l, r]

那么 $f$ 的转移式就能写成： $f[i, l, r]=P(l, r)(F_{i-1}-L[i - 1, l]-R[i - 1, r])$ 。而且最终我们的答案也就是 $F_n$ 。

首先我们可以发现 $L$ 和 $R$ 其实是完全对称的，因此 $L[i, x]=R[i, m-x]$ 。

我们再设 $S[i, r]=\sum\limits_{l\le r}f[i, l, r]$ ，也就是所有右端点在 $r$ 的 $f$ 之和。我们发现对 $S$ 做一遍前缀和就能得到 $L$ ，那么我们只用考虑求出 $S$ 了。我们把 $f$ 的转移方程带入到计算 $S$ 的式子里面：

\begin{aligned} S[i, r]&=\sum\limits_{l\le r}f[i,l, r]\\ &=\sum\limits_{l\le r}P(l, r)(F_{i-1}-L[i - 1, l]-R[i - 1, r])\\ &=D(m-r)\sum_{l\le r} D(l-1)(F_{i-1}-L[i-1, l]-R[i-1, r])\\ &=D(m-r)\left((F_{i-1} - R[i-1, r])\sum_{l\le r}D(l-1)-\sum_{l\le r}D(l-1)L[i-1,l]\right) \end{aligned}

到了这里就比较清楚了，我们可以直接对 $D$ 和 $D(l-1)L[i-1, l]$ 做前缀和，转移就可以做到 $O(1)$ 。而要求 $F_i$ 也直接对 $L[i]$ 做一遍前缀和即可。

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

小 Y 和恐怖的奴隶主

Boss 有 $10^{100}$ 点生命值，它只带了一个随从——一个只有 $m$ 点生命值的“恐怖的奴隶主”。

这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 $\leq 0$ ），且 Boss 的随从数量小于上限 $k$ ，便会召唤一个新的具有 $m$ 点生命值的“恐怖的奴隶主”。

现在进行 $n$ 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 $1$ 点生命值，求出进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。

数据范围： $1 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$ 。

我们发现 $k$ 和 $m$ 很小，稍微权衡一下就能得到状态设计： $f[i, a, b, c]$ 为前 $i$ 次攻击，当前有 $a$ 个 $1$ 血量的随从， $b$ 个 $2$ 血量的随从， $c$ 个 $3$ 血量的随从的概率。

我们可以发现这样只有 $166$ 个状态，允许我们加速递推。

我们很容易就能得到转移方程（下面只用 $m=3$ 来举例）：

设 $add=[a+b+c\not=k]$ ，则有：

f_{i+1, a-1, b, c}\leftarrow \frac{a}{a+b+c+1} f_{i, a, b, c}(a>0)

f_{i+1, a+1, b-1, c+add}\leftarrow \frac{b}{a+b+c+1} f_{i, a, b, c}(b>0)

f_{i+1, a, b+1, c-1+add}\leftarrow \frac{c}{a+b+c+1} f_{i, a, b, c}(c>0)

f_{i+1, a, b, c}\leftarrow \frac{1}{a+b+c+1} f_{i, a, b, c}

而对于伤害的期望，我们可以在转移时记录一个 $g_i$ ，表示第 $i$ 次攻击时期望伤害，让所有 $f_{i, a, b, c}$ 以 $\frac{1}{a+b+c+1}$ 的系数转移过来即可。

我们可以直接预处理递推矩阵的 $2^k$ 次幂，然后每次询问 $O(166^2\log n)$ 即可。

时间复杂度 $O(166^3\log n+T166^2\log n)$ 。

斗主地

一副牌一共有 $n$ 张牌，从上到下依次标号为 $1 - n$ 。标号为 $i$ 的牌分数是 $f(i)$ 。在本题， $f(i)$ 有且仅有两种可能： $f(i) = i$ 或 $f(i) = i^2$ 。

洗牌环节一共分 $m$ 轮，这 $m$ 轮洗牌依次进行。第 $i$ 轮洗牌时：

拿出从最上面往下数的前 $A_i$ 张牌。这样这副牌就被分成了两堆：第一堆是最上面的 $A_i$ 张牌，第二堆是剩下的 $n-A_i$ 张牌，且这两堆牌内相对顺序不变。特别地，当 $A_i = n$ 或 $A_i = 0$ 时，有一堆牌是空的。
接下来对两堆牌进行合并，从而产生新的第三堆牌。当第一堆牌还剩下 $X$ 张，第二堆牌还剩下 $Y$ 张的时候，以 $\dfrac{X}{X+Y}$ 的概率取出第一堆牌的最下面的牌，并将它放入新的第三堆牌的最上面， $\dfrac{Y}{X+Y}$ 的概率取出第二堆牌的最下面的牌，并将它放入新的第三堆牌的最上面
重复操作 $2$ ，一直取到两堆牌都为空为止。这样我们就完成了一轮洗牌。

因为洗牌过程是随机的，所以小 $S$ 发现自己没法知道某个位置上具体是哪张牌。但 crimson000 想问你在经历了这 $m$ 轮洗牌后，某个位置上的牌的期望分数是多少。一共有 $Q$ 个这样的问题。

数据范围： $3\le n \le 10^7$ ， $1\le m,Q\le5\times 10^5$ ， $0\le A_i\le n$ ， $type\in \{1,2\}$ 。

我们先来证明一个结论：经过一轮洗牌后，可能出现的序列的出现概率相同。

我们可以把第一堆的牌看作 $0$ ，第二堆牌看作 $1$ ，而对于题目中的洗牌方式我们可以看作从剩下的所有 $0$ 和 $1$ 中选出一个数放到序列最后。我们考虑给每个点附一个编号，那么这 $n!$ 种排列的出现概率都是相同的。而每一个 $01$ 序列去附编号的方案数都是 $A(n-A)$ ，因此所有序列的出现概率都是相同的。

有了这个结论我们就可以去 dp 了。我们设 $f_{i, j, k}$ 为 $i$ 轮洗牌后第 $j$ 个位置的牌跑到第 $k$ 个位置的概率，我们枚举这一轮中这个牌在哪，再根据我们上面的结论就可以得到下面的转移：

f_{i, j, k}=\sum_{l=1}^{A_i}\frac{\dbinom{k-1}{l-1}\dbinom{n-k}{A_i-l}}{\dbinom{n}{A_i}}f_{i-1, j, l}+\sum_{l=A_i+1}^{n}\frac{\dbinom{k-1}{l-A_i-1}\dbinom{n-k}{n-l}}{\dbinom{n}{A_i}}f_{i-1, j, l}

其中 $\dbinom{k-1}{l-1}\dbinom{n-k}{A_i-l}$ 和 $\dbinom{k-1}{l-A_i-1}\dbinom{n-k}{n-l}$ 的意思是看这个牌和它同一堆的，在它前面的放哪，在它后面的放哪。

这样的时间复杂度是 $O(mn^3)$ 的。我们考虑直接设期望。

我们设 $f_{i, j}$ 为第 $i$ 次打乱后第 $j$ 个位置的期望分数，那么我们可以把上面的转移照搬下来：

f_{i, j}=\sum_{l=1}^{A_i}\frac{\dbinom{j-1}{l-1}\dbinom{n-j}{A_i-l}}{\dbinom{n}{A_i}}f_{i-1, l}+\sum_{l=A_i+1}^{n}\frac{\dbinom{j-1}{l-A_i-1}\dbinom{n-j}{n-l}}{\dbinom{n}{A_i}}f_{i-1, l}

时间复杂度 $O(mn^2)$ 。我们考虑暴力求出来 $t=1, i=1$ 时的 $f$ 值：

\begin{aligned} f_{1, x}&=\sum_{j=1}^{A_1}\frac{\dbinom{x-1}{j-1}\dbinom{n-x}{A_1-j}}{\dbinom{n}{A_1}}\times j+\sum_{l=A_1+1}^{n}\frac{\dbinom{x-1}{j-A_1-1}\dbinom{n-x}{n-j}}{\dbinom{n}{A_1}}\times j\\ \end{aligned}

我们发现左右两边长得差不多，我们只单独弄出来左半边来。

\begin{aligned} \sum_{j=1}^{A_1}\frac{\dbinom{x-1}{j-1}\dbinom{n-x}{A_1-j}}{\dbinom{n}{A_1}}\times j&=\sum_{j=1}^{A_1}\frac{\dbinom{x-1}{j-1}\dbinom{n-x}{A_1-j}}{\dbinom{n}{A_1}}\times (j-1)+\sum_{j=1}^{A_1}\frac{\dbinom{x-1}{j-1}\dbinom{n-x}{A_1-j}}{\dbinom{n}{A_1}}\\ &=\sum_{j=1}^{A_1}\frac{\dbinom{x-2}{j-2}\dbinom{n-x}{A_1-j}}{\dbinom{n}{A_1}}\times (x-1)+\frac{\dbinom{n-1}{A_1-1}}{\dbinom{n}{A_1}}\\ &=\frac{\dbinom{x-2}{A_1-2}}{\dbinom{n}{A_1}}\times (x-1)+\frac{\dbinom{n-1}{A_1-1}}{\dbinom{n}{A_1}}\\ \end{aligned}

我们发现最终的式子只和 $x$ 线性相关，那么我们可以把 $kx+b$ 再带入 $f_2$ 中，我们依旧能得到相同的结论。因此我们就能证明 $f_m(x)$ 为关于 $x$ 的一次函数。

而对于 $t=2$ ，我们可以把二次式化为 $a(x-1)(x-2)+b(x-1)+c$ ，然后和上面一样推式子，我们可以证明它依旧是一个二次函数。我们就可以递推出 $f_m$ 的系数，每次询问 $O(1)$ 回答即可。

时间复杂度 $O(n+m+k)$ 。

[ZJOI2017] 树状数组

漆黑的晚上，crimson001 躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的 OI 比赛经历。那是一道基础的树状数组题。

给出一个长度为 $n$ 的数组 $A$ ，初始值都为 $0$ ，接下来进行 $m$ 次操作，操作有两种：

$1\ x$ ，表示将 $A_x$ 变成 $(A_x + 1) \bmod 2$ 。
$2\ l\ r$ ，表示询问 $(\sum_{i=l}^r A_i) \bmod 2$ 。

尽管那个时候的 crimson001 非常的 simple，但是她还是发现这题可以用树状数组做。当时非常 young 的她写了如下的算法：

void add(int x, int v)
{
	for(; x; x -= lowbit(x)) c[x] = (c[x] + 1) % 2;
}

int find(int x)
{
	if(x == 0) return 0;
    int ans = 0;
    for(; x <= n; x += lowbit(x)) ans = (ans + c[x]) % 2;
    return ans;
}

int Query(int l, int r)
{
    int ansl = find(l - 1);
    int ansr = find(r);
    return (ansr - ansl + 2) % 2;
}

如果你对树状数组比较熟悉，不难发现可怜把树状数组写错了： $\text{Add}$ 和 $\text{Find}$ 中 $x$ 变化的方向反了。因此这个程序在最终测试时华丽的爆 0 了。

然而奇怪的是，在当时，这个程序通过了出题人给出的大样例——这也是 crimson001 没有进行对拍的原因。

现在，crimson001 想要算一下，这个程序回答对每一个询问的概率是多少，这样她就可以再次的感受到自己是一个多么非的人了。然而时间已经过去了很多年，即使是 crimson001 也没有办法完全回忆起当时的大样例。幸运的是，她回忆起了大部分内容，唯一遗忘的是每一次第一类操作的 $x$ 的值，因此她假定这次操作的 $x$ 是在 $[l_i, r_i]$ 范围内等概率随机的。

具体来说，crimson001 给出了一个长度为 $n$ 的数组 $A$ ，初始为 $0$ ，接下来进行了 $m$ 次操作：

$1\ l\ r$ ，表示在区间 $[l, r]$ 中等概率选取一个 $x$ 并执行 $\text{Add}(x)$ 。
$2\ l\ r$ ，表示询问执行 $\text{Query}(l, r)$ 得到的结果是正确的概率是多少。

数据范围： $n, m\le 10^5$ 。

我们转化完题意就能发现，我们要求的其实就是 $a_{l-1}=a_r$ 的概率。我们设 $p_{x, y}$ 为 $a_x=a_y$ 的概率，进行一个分类讨论。

当 $x<l,l\le y\le r$ 时， $a_x$ 和 $a_y$ 相同情况变化的概率为 $\frac{1}{r-l+1}$ 。
当 $l\le x\le r, r<y$ 时，变化的概率为 $\frac{1}{r-l+1}$ 。
当 $l\le x<y\le r$ 时，变化的概率为 $\frac{2}{r-l+1}$ 。
这里还有一个特殊情况为 $l=1$ $l = 1$ 时，这次这一次询问答案不变就等价于 $sum_{1\sim r}=sum_{r\sim n}$ $s u m_{1 \sim r} = s u m_{r \sim n}$ 。那么再对这种情况分类讨论：
- 当 $x=1, l\le y\le r$ 时，变化的概率为 $\frac{r-l}{r-l+1}$ 。
- 当 $y<l$ 或 $y>r$ 时，变化的概率是 $1$ 。

于是我们可以用树套树来维护。设当前操作不变的概率为 $q$ ，原先相等的概率为 $p$ ，那么新的相等的概率为 $pq+(1-p)(1-q)$ 。树套树标记永久化一下即可。

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

Sonya and Informatics

给一个长度为 $n$ 的 $01$ 串，进行 $k$ 次操作，每次操作选择两个位置 $i,j$ ，交换 $i,j$ 上的数，求 $k$ 次操作后，该 $01$ 串变成非降序列的概率。

数据范围： $n\le 100,k\le 10^9$ 。

我们求出变为非降序列的方案数，最后除以 $\left(\frac{n(n-1)}{2} \right)^k$ 即为概率。假设序列中有 $m$ 个 $0$ ，那么最终的序列前面一定是有 $m$ 个 $0$ 的，我们就用这一点来表示当前的状态。

我们设 $f_{i, j}$ 为 $i$ 次操作，前 $m$ 个位置里有 $j$ 个 $0$ 的方案数。转移我们就考虑如何让前面的 $0$ 跑到后面或者让后面的 $0$ 跑到前面即可。转移如下：

f_{i+1, j+1}\leftarrow (m-j)^2f_{i, j}

f_{i+1, j-1}\leftarrow j\times (n-2m+j)f_{i, j}

f_{i+1,j}\leftarrow (\frac{n}{2}-(m-j)^2-j\times (n-2m+j))\times f_{i, j}

我们可以矩阵加速递推。时间复杂度 $O(n^3\log k)$ 。

Boring Problem（gym103119B）

定义 $F(S, T, p)$ 为：给定一个长度为 $|S|$ 的字符串 $S$ 和 $n$ 个长度为 $m$ 的字符串 $T_i$ ，字符集大小为 $k$ ，每次向 $S$ 后以 $p_i$ 的概率添加一个字符 $i$ 。直到存在 $T_j$ 为 $S$ 的子序列时停止，这时 $S$ 的期望长度。

现在给定你 $T_i$ 和一个字符串 $R$ 以及添加字符的概率 $p$ ，对于 $R$ 的每一个前缀（长度为 $i$ 的前缀记为 $R_i$ ），求出 $F(R_i, T, p)$ 。

数据范围： $n\le 100, n\times m\le 10^4, k\le 26, |R|\le 10^4$ 。

这种往后填字符一般有两种做法：PGF 和直接期望 dp。这里我们进行一个期望 dp，因为题目中是要对所有 $R$ 的前缀都求一遍，我们只需要在 AC 自动机上跑前缀即可。

我们先建出来 AC 自动机，设 $E_i$ 为 AC 自动机上编号为 $i$ 的点到一个终止状态的期望步数。转移显然，我们设 $tr_{i, c}$ 为 $i$ 点的第 $c$ 个儿子，那么转移为：

E_u=\sum_{c=1}^{k} p_c\times E_{tr_{u, c}} + 1

我们发现这样是有后效性的，要高斯消元，时间复杂度 $O((nm)^3)$ ，显然过不去。

设 $x$ 的第 $c$ 个儿子是 $y$ （且这条转移存在），我们进行一个移项：

E_y=\frac{1}{p_c}\left(E_x-\sum_{c'\not= c}p_{c'}\times E_{tr_{x, c'}}-1 \right)

我们发现 $y$ 的期望只和它的父亲以及它的兄弟相关，考虑缩减未知数数量。我们选取 $x$ 的任意一个儿子 $y$ ，让剩下的儿子成为未知数，那么如果我们用这些未知数表示出了深度小于 $d$ 的点，那么对于某个深度等于 $d$ 的点一定可以用自己表示（新开一个未知数）或者用它的兄弟以及深度小于 $d$ 的点来表示。这样未知数的数量是分叉的个数，我们再用叶子的期望为 $0$ 列出 $n$ 个方程高斯消元即可。

时间复杂度 $O(n^3+n^2mk+|R|)$ 。

CF963E

在平面直角坐标系上，有一个的点一开始在 $(0, 0)$ 。每秒钟这个点都会随机移动：如果它在 $(x, y)$ ，下一秒它在 $(x - 1, y)$ 的概率是 $p_1$ ，在 $(x, y - 1)$ 的概率是 $p_2$ ，在 $(x + 1, y)$ 的概率是 $p_3$ ，在 $(x, y + 1)$ 的概率是 $p_4$ 。保证 $p_1 + p_2 + p_3 + p_4 = 1$ ，各次移动互不关联。