题意：一次找一个bug，问所有的bug能覆盖n中类型和s个子系统，需要找的次数的期望是多少。

对于两相互独立的事件 $P(X)$ 和 $P(Y)$，任意$x$和$y$而言有离散随机变量 $ P(X = x , and , Y = y) = P(X = x) \cdot P(Y = y) $，这条题目注意要计算联合分布，使用全概率公式。

一个错误的思路

设$e[i][j]$为覆盖$i$种bug和$j$个系统需要找的次数的期望，本题要求$e[n][s]$。
$e[i][j]$可有4种（注意其他DP做多了很容易想成3种）

$e[i-1][j]$，新bug，重复的系统
$$
p_{up} = \frac{(n - i + 1) * j}{n * s} \\
from_{up} = p_{up} * (e[i-1][j])
$$

注意不能写成$(e[i-1][j] + 1)$这样的形式，而要在最后统一加上$1$。
$$
e_{up} + e_{left} + e_{diag} + 1
$$
因为根据期望的定义，$e[i-1][j]$作为期望实际上是带了命中$(i-1, j)$这种情况的概率$p[i-1][j]$，所以我们要加上的“$1$”应该再乘上一个$p[i-1][j]$。

$e[i][j-1]$，重复的bug，新系统
$$
p_{left} = \frac{i * (s - j + 1)}{n * s } \\
from_{left} = p_{left} * (e[i][j-1])
$$
$e[i-1][j-1]$，新bug，新系统
$$
p_{diag} = \frac{(n - i + 1) * (s - j + 1)}{n * s } \\
from_{diag} = p_{diag} * (e[i-1][j-1])
$$
$e[i][j]$，重复的bug，重复的系统
$$
p_{rep} = \frac{i * j}{n * s } \\
from_{rep} = p_{rep} * e[i][j]
$$
这种情况很容易丢掉

注意$ + 1$不能写成$(e[i-1][j] + 1)$这样的形式，因为$e[i-1][j]$作为期望实际上是带了命中$(i-1, j)$这种情况的概率的，所以要在最后统一加上$1$。
考虑最容易丢掉的第四种情况，如果我们把它加到我们DP等式的右部，这会使我们的DP进入一个环，这是行不通的。正确方法是由于是要求$dp[i][j]$，所以我们当做方程来解。
$$
(1 - p_{rep}) * e[i][j] = from_{up} + from_{left} + from_{diag} + 1
$$
令$(i, j) = (n, s)$，我们发现，左部等于0，但右部不等于0，这是矛盾的。

正确的思路

一般求概率应该正推，求期望应该逆推。求期望如果顺推不仅麻烦，还会出现重复计算的情况。
例如以样例1 2来看，其期望应该是$1 + 1 + 1/2 + 1/4 + … + 1/2^n = 3$
本题应该逆推，假设$e[i][j]$为覆盖$i$种bug和$j$个系统时需要找的次数的期望，则$e[n][s] = 0$，那我们是要求的$e[0][0]$。其实对于大多数概率DP的题目都是要逆推，求的是初始条件。

$e[i][j]$同样有4种

$e[i-1][j]$，新bug，重复的系统
$$
p_{down} = \frac{(n - i + 1) * j}{n * s} \\
from_{down} = p_{down} * e[i-1][j]
$$
$e[i][j-1]$，重复的bug，新系统
$$
p_{right} = \frac{i * (s - j + 1)}{n * s } \\
from_{right} = p_{right} * e[i][j-1]
$$
$e[i-1][j-1]$，新bug，新系统
$$
p_{diag} = \frac{(n - i + 1) * (s - j + 1)}{n * s } \\
from_{diag} = p_{diag} * e[i-1][j-1]
$$
$e[i][j]$，重复的bug，重复的系统
$$
p_{rep} = \frac{i * j}{n * s } \\
from_{rep} = p_{rep} * e[i][j]
$$