模拟赛

T1

不清楚，润

感觉可以状压

哦好像确实可行

考虑设 $f_{i,S}$ 表示当前在第 $i$ 行，从左侧继承而来的集合为 $S$

不妨设 $2nm-n-m=S$

一条边出现一次的概率是 $\frac{1}{S}$ ，两次则为 $\frac{1}{S^2}$

则一条边出现的概率为 $$\sum_{i=1}^{+\infty}\frac{1}{S^i}$$
而我们有

$$\sum_{i=1}^{+\infty}\frac{1}{S^i}-\frac{1}{S}\sum_{i=1}^{+\infty}\frac{1}{S^i}=\frac{1}{S}$$
所以有

$$\sum_{i=1}^{+\infty}\frac{1}{S^i}=\frac{1}{S-1}$$

T2

考虑反过来想

因为答案只与结果有关，而不在乎中间过程，所以我们考虑确定终止状态后如何去用最小代价将其构造出来

首先最右侧的元素一定是两个连续的，证明显然

于是就可以唯一确定一个左移一格的元素，递归成子问题解决

其次可以证明，过程中一定不会出现四个连在一起的情况(数学归纳法)

因此递推回一列时最多有两个元素，且两元素相邻

但是这样可能会出现一些问题，比如说三个相连的情况

此时只有一种可能：这是之前元素补位上来的，但是这种情况下会产生一个类似“倒勾”的东西，也就意味着下面的拓展其实是有限的

所以我们可以对序列进行分段，考虑设 $f_{i}$ 表示用了 $i$ 次，末尾位置为 $2$ 的方案数

你发现其实所有的方案回归到本质上都是倒勾

每段二其实只有两种选择，一种是形成一个长倒勾，另一种是形成一个双倒勾

所以我们就有了状态转移方程

J:从何处转移，那么就还剩余 $i-j-1$ 次操作

$$

f_i=f_{i-1}+\sum_{j=1}^{i-1}f_{j}\times\left\lceil \frac{i-j-1}{2} \right\rceil

$$

$$f_{i,j}=f_{i-1,j+1}+f_{i-1,j-1}+\sum_{k=3}^{}f_{i-3-(2k-1),j+1}$$

感觉像矩阵快速幂

容易发现每一列最多只会进行两次分裂，所以考虑同时记录两段的矩形

然后就做完了？

$$\begin{bmatrix}0000 & 0001 & 0010 & 0011\
0100 & 0101 & 0110 & 0111\
1000 & 1001 & 1010 & 1011\
1100 & 1101 & 1110 & 1111\
0000 & 0001 & 0010 & 0011\
0100 & 0101 & 0110 & 0111\
1000 & 1001 & 1010 & 1011\
1100 & 1101 & 1110 & 1111\
\end{bmatrix}$$
$$\begin{bmatrix}\end{bmatrix}$$

下午

![[构造选讲_无题解.pdf]]

$$\subset \subseteq $$