还没写完
A. 岛屿
题意简述：有 \(2n\) 个岛。给定 \(x, y\)，其中 \(2x+y=n\)。已知岛 \(i, i+n\) 之间有连边。\([1, x] \cup [n+1,2n-x]\) 的岛是红色，其余是白色。现在要添加 \(n\) 条边，每条边的两个端点的颜色不能相同。求图中的期望连通块数量。
若我们将 \([1, n]\) 和 \([n + 1, 2n]\) 的岛分别看作一组，那么这两组的前 \(x\) 个元素形如 \(1-1\)，中间 \(y\) 个形如 \(0-1\)，后 \(x\) 个形如 \(0-0\)。
\[1,1,1,1,0,0,0,0,0,0\\ 1,1,1,1,1,1,0,0,0,0 \]比如这个例子中 \(x = 4, y = 2\)。
因为两组中的对应位置间初始已经有连边，即每个点的度数均为 \(1\)。此时要新加 \(n\) 条边，且边的端点互不相同，也就是说新图中每个点的度数都应该增加 \(1\)，即为 \(2\)。而如果一个连通块中所有点的度数均为 \(2\) 则这个连通块是一个环。问题变成求图中环的期望数量。
设计 DP 状态 \(f(A, B, C)\) 表示有 \(A\) 个 \(1-1\)，\(B\) 个 \(0-0\)，\(C\) 个 \(0-1\) 的期望环的数量。那么答案为 \(f(x, x, y)\)。
考虑转移。
-
\(C = 0\)：
即只有 \(A\) 个 \(1-1\) 和 \(B\) 个 \(0-0\)。因为能加的边的两端点的颜色不能相同，所以不能在 \(A, B\) 内部连边，即要从 \(A, B\) 中分别选一条边相连。而连接后 \(1-1-0-0\) 可以视作 \(1-0\) 边，而 \(1-1,0-0\) 边的数量分别减少。即 \(f(A, B, 0) = f(A - 1, B - 1, 1)\)。
-
\(C > 0\)：
我们考虑分析第一条 \(0-1\) 边。
-
如果连自环，即在这两个点间再加一条边，那么环数会增加 \(1\)，\(0-1\) 边数量会减少 \(1\)。概率为 \(\dfrac 1{A+B+C}\)。
-
如果这条 \(0-1\) 边与另一条 \(0-1\) 边相连，那么 \(0-1-0-1\) 将合并成 \(0-1\)，即 \(0-1\) 边数量减少 \(1\)。概率为 \(\dfrac{C-1}{A+B+C}\)。
-
如果这条 \(0-1\) 边的 \(0\) 与另一条 \(1-1\) 边的 \(1\) 相连，那么 \(1-0-1-1\) 可以看作 \(1-1\)。\(1-1\) 边数量减少 \(1\) 又增加 \(1\) 相当于不变，而 \(0-1\) 边的数量减少 \(1\)。概率为 \(\dfrac A{A+B+C}\)。
-
如果这条 \(0-1\) 边的 \(1\) 与另一条 \(0-0\) 边的 \(0\) 相连，与上面类似，\(0-0\) 边数量减少 \(1\) 又增加 \(1\) 相当于不变，而 \(0-1\) 边的数量减少 \(1\)。概率为 \(\dfrac B{A+B+C}\)。
综上 \(f(A, B, C) = \dfrac1{A+B+C} (f(A,B,C-1)+1) + \dfrac{C-1}{A+B+C}f(A,B,C-1) + \dfrac A{A+B+C}f(A,B,C-1) + \dfrac B{A+B+C}f(A,B,C-1)\)。化简后是 \(f(A,B,C) = f(A,B,C-1)+\dfrac1{A+B+C}\)。
-
综上：
\[f(A,B,C) = \left\{ \begin{matrix} f(A-1,B-1,1) &,C=0 \\ f(A , B, C - 1) + \dfrac1{A+B+C} &,C \ne 0\end{matrix}\right. \]你发现从 \(f(x,x,y)\) 开始 DP 能用到的 DP 状态都满足 \(A = B\)，所以可以进一步优化成二维：
\[f(A,C) = \left\{ \begin{matrix} f(A-1,1) &,C=0 \\ f(A, C - 1) + \dfrac1{2A+C} &,C \ne 0\end{matrix}\right. \] 标签：matrix,减少,dfrac,dfrac1,9.2,2n,数量,模拟 From： https://www.cnblogs.com/2huk/p/18393093