前言

省流：300 分。

T1

考虑 DP，设 $f(i,0/1/2)$ 表示处理到第 $i$ 个数，当前是往左，不动，往右，方案是否合法，转移如下：

\begin{aligned} f[i][0] &= f[i-1][0] \cdot [x_i - x_{i-1} = 1] + f[i-1][1] \cdot [x_i - (x_{i-1} - 1) = 1] + f[i-1][2] \cdot [x_i - (x_{i-1} + 1) = 1], \\ f[i][1] &= f[i-1][0] \cdot [x_i - 1 - x_{i-1} = 1] + f[i-1][1] \cdot [x_i - 1 - (x_{i-1} - 1) = 1] + f[i-1][2] \cdot [x_i - 1 - (x_{i-1} + 1) = 1], \\ f[i][2] &= f[i-1][0] \cdot [x_i + 1 - x_{i-1} = 1] + f[i-1][1] \cdot [x_i + 1 - (x_{i-1} - 1) = 1] + f[i-1][2] \cdot [x_i + 1 - (x_{i-1} + 1) = 1], \end{aligned}

$O(n)$ 。

$O(1)$ 做法：直接判断 $a_n-a_{1}\le n+1$ 即可。

T2

原题 CF1824B2 LuoTianyi and the Floating Islands (Hard Version) - 洛谷

T3

四元环计数，考虑和三元环计数一样，先度数小的往度数大的定向。

不难发现只有三种情况：

A -> B -> C -> D
A -> B -> D -> C
A -> D -> B -> C

考虑固定 $A$ ，让后我们对于后面三个进行暴力枚举，不难发现后面三个相当于在枚举三元环，时间复杂度是 $O(m\sqrt{m})$ 。

有必要澄清一点的是，loj 的提交是因为我根本不知道样例合法性，有好心人说样例有误我也只能自己猜样例这样改应该是对的，不算分。

T4

一眼 $n$ 极大 $m,k$ 极小，考虑矩阵快速幂。

先把 DP 设出来，由于 $k$ 极小可以直接在状态内部表示我们恐怖的奴隶主的类型，设 $f(i,cnt1,cnt2,cnt3)$ 表示目前打到第 $i$ 轮，恐怖的奴隶主剩一滴血的数量为 $cnt1$ ，两滴血的为 $cnt2$ ，三滴血的为 $cnt3$ ，的扣减 Boss 的生命值点数的期望。先写出打 4 种怪的概率：

打 Boss： $p_0=\dfrac{1}{cnt1+cnt2+cnt3+1}$ 。
打一滴血的： $p_{1}=\dfrac{cnt1}{cnt1+cnt2+cnt3+1}$ 。
打两滴血的： $p_{2}=\dfrac{cnt2}{cnt1+cnt2+cnt3+1}$ 。
打三滴血的： $p_{3}=\dfrac{cnt3}{cnt1+cnt2+cnt3+1}$ 。

那么转移如下，令 $nowf=f(i,cnt1,cnt2,cnt3)$ ：

f(i+1,cnt1,cnt2,cnt3)\leftarrow nowf+p_0

\begin{aligned} f(i+1,cnt1-1,cnt2,cnt3) & \leftarrow nowf\cdot p_{1} & (cnt1\neq 0) \\ \\ f(i+1,cnt1+1,cnt2-1,cnt3+1) & \leftarrow nowf\cdot p_{2} & (cnt1+cnt2+cnt3 \le k) \\ f(i+1,cnt1+1,cnt2-1,cnt3) & \leftarrow nowf\cdot p_{2} & (cnt1+cnt2+cnt3 > k) \\ \\ f(i+1,cnt1,cnt2+1,cnt3) & \leftarrow nowf\cdot p_{3} & (cnt1+cnt2+cnt3 \le k) \\ f(i+1,cnt1,cnt2+1,cnt3-1) & \leftarrow nowf\cdot p_{3} & (cnt1+cnt2+cnt3 > k) \\ \end{aligned}

时间复杂度 $O(nk)$ ，爆搜发现有效的状态数上界 $k$ 很小，在 170 左右，用矩阵快速幂简单优化可以做到 $O(Tk^3 \log n)$ ，发现炸掉了，考虑优化。

首先向量乘法是 $k^2$ 的，所以简单实现向量乘法而不是矩阵乘法容易有 $O(Tk^2(k^3 \log n)$ ，发现瓶颈在于每一次我们都要算一遍转移矩阵。注意到 $m,k$ 固定而 $n$ 才是变化的。所以预处理转移矩阵，通过二进制分组转移即可，时间复杂度 $O(k^3 \log n+Tk^2 \log n)$ 。

反思：矩阵乘法实现的时候应当注意有效状态的数量以及矩阵乘法带来的 $n^3$ 的大小，这个一定是要注意的。