Probability

-   公主抓到一只白鼠，公主赢了．概率为 $\dfrac{i}{i+j}$．
-   公主抓到一只黑鼠，龙抓到一只白鼠，龙赢了．概率为 $\dfrac{j}{i+j}\cdot\dfrac{i}{i+j-1}$．
-   公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，转移到 $f_{i,j-3}$．概率为 $\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{j-2}{i+j-2}$．
-   公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，转移到 $f_{i-1,j-2}$．概率为 $\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{i}{i+j-2}$．

考虑公主赢的概率，第二种情况不参与计算．并且要保证后两种情况合法，所以还要判断 $i,j$ 的大小，满足第三种情况至少要有 3 只黑鼠，满足第四种情况要有 1 只白鼠和 2 只黑鼠．

考虑 $f_{i,j}$ 的状态转移：

-   $f_{i,j}$，发现一个 bug 属于已经发现的 $i$ 种 bug 分类，$j$ 个子系统，概率为 $p_1=\dfrac{i}{n}\cdot\dfrac{j}{s}$．
-   $f_{i,j+1}$，发现一个 bug 属于已经发现的 $i$ 种 bug 分类，不属于已经发现的子系统，概率为 $p_2=\dfrac{i}{n}\cdot(1-\dfrac{j}{s})$．
-   $f_{i+1,j}$，发现一个 bug 不属于已经发现 bug 分类，属于 $j$ 个子系统，概率为 $p_3=(1-\dfrac{i}{n})\cdot\dfrac{j}{s}$．
-   $f_{i+1,j+1}$，发现一个 bug 不属于已经发现 bug 分类，不属于已经发现的子系统，概率为 $p_4=(1-\dfrac{i}{n})\cdot(1-\dfrac{j}{s})$．

再根据期望的线性性质，就可以得到状态转移方程：

$$
\begin{aligned}
f_{i,j} &= p_1\cdot f_{i,j}+p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1} + 1\\
&= \dfrac{p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1}+1}{1-p_1}
\end{aligned}
$$

定义 $f_{i,j,0/1}$ 为在第 $i$ 个时间段，连同这一个时间段已经用了 $j$ 次换教室的机会，在这个时间段换（1）或者不换（0）教室的最小期望路程和，那么答案就是 $\min \{f_{n,i,0},f_{n,i,1}\} ,i\in[0,m]$．注意边界 $f_{1,0,0}=f_{1,1,1}=0$．

考虑 $f_{i,j,0/1}$ 的状态转移：

-   如果这一阶段不换，即 $f_{i,j,0}$．可能是由上一次不换的状态转移来的，那么就是 $f_{i-1,j,0}+w_{c_{i-1},c_{i}}$, 也有可能是由上一次交换的状态转移来的，这里结合条件概率和全概率的知识分析可以得到 $f_{i-1,j,1}+w_{d_{i-1},c_{i}}\cdot p_{i-1}+w_{c_{i-1},c_{i}}\cdot (1-p_{i-1})$，状态转移方程就有：

$$
\begin{aligned}
f_{i,j,0}=min(f_{i-1,j,0}+w_{c_{i-1},c_{i}},f_{i-1,j,1}+w_{d_{i-1},c_{i}}\cdot p_{i-1}+w_{c_{i-1},c_{i}}\cdot (1-p_{i-1}))
\end{aligned}
$$

-   如果这一阶段交换，即 $f_{i,j,1}$．类似地，可能由上一次不换的状态转移来，也可能由上一次交换的状态转移来．那么遇到不换的就乘上 $(1-p_i)$，遇到交换的就乘上 $p_i$，将所有会出现的情况都枚举一遍出进行计算就好了．这里不再赘述各种转移情况，相信通过上一种阶段例子，这里的状态转移应该能够很容易写出来．

-   $f_{i,1}=\dfrac{1}{3}\cdot(f_{i+1,1}+f_{i,2}+f_{i,1})+1$
-   $f_{i,j}=\dfrac{1}{4}\cdot(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1$
-   $f_{i,m}=\dfrac{1}{3}\cdot(f_{i,m}+f_{i,m-1}+f_{i+1,m})+1$

在行之间由于只能向下移动，是满足无后效性的．在列之间可以左右移动，在移动过程中可能产生环，不满足无后效性．
将方程变换后可以得到：

-   $2f_{i,1}-f_{i,2}=3+f_{i+1,1}$
-   $3f_{i,j}-f_{i,j-1}-f_{i,j+1}=4+f_{i+1,j}$
-   $2f_{i,m}-f_{i,m-1}=3+f_{i+1,m}$

由于是逆序的递推，所以每一个 $f_{i+1,j}$ 是已知的．
由于有 $m$ 列，所以右边相当于是一个 $m$ 行的列向量，那么左边就是 $m$ 行 $m$ 列的矩阵．使用增广矩阵，就变成了 $m$ 行 $m+1$ 列的矩阵，然后进行 [高斯消元](../math/numerical/gauss.md) 即可解出答案．