20220118

哈哈输出大样例能得的分都比打了 3.5h 得分高。

# A. 「清华集训 2017」小 Y 和恐怖的奴隶主

期望 dp + 矩阵乘法

看完题之后比较晕，没有想到把 1，2，3 血的怪的数量都记录下来，整个 4 维期望 dp，直接跳过了，有点亏。

设状态 $dp[i][a][b][c]$，表示打了 $i$ 次之后场上 1，2，3 血的怪物分别有 $a, b, c$ 只。

暴力转移显然会 TLE。

不难发现，总共只有 165 个状态，加上答案状态就是 166 个状态，所以可以编个号，然后压到一维里，使用矩乘加速。

code

# B. 「一本通 4.4 练习 4」跳跳棋

巨大难思维 + LCA

谁能想到这题跳棋的情况可以建成一棵树？？？

20pts bfs 暴力滚粗。

注意题目里：一次只允许跳过一个棋子。

（考场上虽然看到了，但是没反应过来，还以为是只能跳一次的意思……）

所以中间的点可以向两边跳，两边的点只有一个能往中间跳（只有距离中间那个点近的点可以向中间跳）。

把三个点的位置三元组 $(x, y, z)$ 存到一个节点里，那么是如何建树的呢？

把向中间跳的那个三元组当父亲节点，向外跳的两个当儿子节点，然后两点之间的距离就是跳的次数。

但是怎么快速求 LCA 呢？三元组普通的倍增什么的是不行的，所以先把深度大的点跳到跟另一个点深度相同的高度，然后二分向上跳的步数，再判断。

code

# C. Calc

dp + 拉格朗日插值

先考虑暴力 dp

设 $dp_{i, j}$ 表示前 $i$ 个数用了 $1 \sim j$ 的和，转移方程比较显然：

我们只处理递增的序列，分类讨论第 $i$ 个数取不取 $j$。

$$dp_{i, j} = dp_{i - 1, j - 1} \times j + dp_{i, j - 1}$$

经过一系列推导，我们发现 $dp_{n, i}$ 是关于 $i$ 的一个 $2n$ 次多项式，所以直接拉格朗日插值求一下 $dp_{n, A}$ 即可。

code