菜王的 blog

• A 过水不讲。

• B 过水不讲。

• C 过水不讲。

• D 背包模板，过水不讲。

• E 由于这一题背包容量过大，但是价值很小，所以我们可以根据价值来 DP。设 $f_{i, j}$ 为前 $i$ 个物品，获得 $j$ 的价值所需要的最小容量，$ans$ 即为满足 $f_{n, ans} \le m$ 的最大 $ans$。

• F LCS 模板，过水不讲。

• G 拓扑排序模板，过水不讲。

• H 过水不讲。

• I 设 $f_{i, j}$ 为前 $i$ 枚硬币有 $j$ 枚硬币正面朝上的概率。转移有 $f_{i, j} = p_i \times f_{i, j - 1} + (1 - p_i) \times f_{i, j}$。

• J 由于 $a_i$ 最多为 $3$，所以我们可以推出状态：$f_{a, b, c}$ 代表还剩 $a$ 个 $3$ 个寿司的盘子，$b$ 个 $2$ 个寿司的盘子，$c$ 个 $1$ 个寿司的盘子，有转移：

$f_{a, b, c} = \frac{a}{n}(f_{a - 1, b + 1, c} + 1) + \frac{b}{n}(f_{a, b - 1, c + 1} + 1) + \frac{c}{n}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{n}(f_{a, b, c} + 1)$

我们发现，这个屑转移方程会自己转移到自己，怎么办呢？给它变形。

$f_{a, b, c} = \frac{a}{n}(f_{a - 1, b + 1, c} + 1) + \frac{b}{n}(f_{a, b - 1, c + 1} + 1) + \frac{c}{n}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{n}f_{a, b, c} + \frac{n - a - b - c}{n}$

$f_{a, b, c} - \frac{n - a - b - c}{n}f_{a, b, c} = \frac{a}{n}(f_{a - 1, b + 1, c} + 1) + \frac{b}{n}(f_{a, b - 1, c + 1} + 1) + \frac{c}{n}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{n}$

$\frac{a + b + c}{n}f_{a, b, c} = \frac{a}{n}(f_{a - 1, b + 1, c} + 1) + \frac{b}{n}(f_{a, b - 1, c + 1} + 1) + \frac{c}{n}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{n}$

$f_{a, b, c} = \frac{n}{a + b + c}\left(\frac{a}{n}(f_{a - 1, b + 1, c} + 1) + \frac{b}{n}(f_{a, b - 1, c + 1} + 1) + \frac{c}{n}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{n}\right)$

$f_{a, b, c} = \frac{a}{a + b + c}(f_{a - 1, b + 1, c} + 1) + \frac{b}{a + b + c}(f_{a, b - 1, c + 1} + 1) + \frac{c}{a + b + c}(f_{a, b, c - 1} + 1) + \frac{n - a - b - c}{a + b + c}$

这样就可以直接 DP 了，时间复杂度为 $O(n^3)$。

• K 博弈论 DP。设 $f_{i, 0 / 1}$ 为堆里还剩 $i$ 块石头，Taro / Jiro 先操作，Taro 的输赢情况。（$1$ 表示赢）由于 Taro 想让自己尽可能地赢，所以 $f_{i, 0} = \bigvee_{j = 1}^n f_{i - a_j, 1}$。Jiro 想让 Taro 尽可能输（也就是让自己尽可能赢），所以 $f_{i, 1} = \bigwedge_{j = 1}^n f_{i - a_j, 0}$。特别的，如果对于每一个 $j$，$i - a_j$ 都小于 $0$，那么要让另外一个选手赢。

• L 博弈论，区间 DP。设 $f_{l, r}$ 为取到只剩区间 $[l, r]$ 的元素，Taro 先手能获得的最大得分差，$g_{l, r}$ 为取到只剩区间 $[l, r]$ 的元素，Jiro 先手能获得的最小得分差。枚举当前取走 $l$ 还是 $r$，随便转移一下即可。

• M 前缀和优化 DP。设 $f_{i, j}$ 为前 $i$ 个孩子分了 $j$ 块糖果的方案数，转移为 $f_{i, j} = \sum_{k = j - a_i}^j f_{i - 1, k}$，时间复杂度为 $O(nk^2)$，会超时。再设 $sum_{i, j} = \sum_{k = 0}^j f_{i, k}$，就可以做到 $O(nk)$ 了。

• N 原题 P1775，不讲。

• O 状压 DP。设 $f_{i, j}$ 为目前给前 $i$ 个男人配对，且女人的配对情况为 $j$ 时方案数。枚举第 $i$ 个男人与哪个女人配对，转移为 $f_{i, j} = \sum_{k = 1}^n [j \& 2^{k - 1}] \times a_{i, k} \times f_{i, j \oplus 2^{k - 1}}$。时间复杂度为 $O(n^2 \times 2^n)$，会超时。

  我们考虑去除无用状态。由于题目要求的是 $n$ 个男人和 $n$ 个女人配对的方案数，而且每个男人只能配对一个女人，所以 $i \not= \operatorname{popcnt}(j)$ 的 $f_{i, j}$ 都是无用状态。时间复杂度降至 $O(n \times 2^n)$，可以通过。

• P 类似于没有上司的舞会，设 $f_{u, 0 / 1}$ 为 $u$ 点选 / 不选的方案数，转移为 $f_{u, 0} = \prod_{v \in \operatorname{son}(u)} f_{v, 0} + f_{v, 1}$，$f_{u, 1} = \prod_{v \in \operatorname{son}(u)} f_{v, 0}$（子树之间不会互相影响，满足乘法原理）。

• Q 树状数组优化 DP（当然用线段树也可以）。设 $f_i$ 为 LIS 最后一个元素为 $a_i$ 的最大价值，可以列出转移 $f_i = \max_{j = 1}^{i - 1}\{[a_i > a_j]f_j\} + b_i$。转移的限制有两个，第一个是下标的限制，第二个是 $a_i$ 的限制。第一个限制只需要在每次转移后，将 $f_i$ 插入即可。而第二个限制可以在 $a_i$ 的位置插入 $f_i$，转移时用树状数组查询 $[1, a_i - 1]$ 的前缀最大值即可。

• R 矩阵快速幂优化递推。设 $f_{i, j}$ 为长度为 $i$，终点为 $j$ 的路径数。有转移方程 $f_{i, j} = \sum_{k = 1}^n e_{k, j} \times f_{i - 1, k}$，时间复杂度为 $O(n^2K)$。

  我们发现这个柿子有点像矩阵乘法的形式，于是我们可以写出初始矩阵 $B$ 为 $\begin{bmatrix}1 & 1 & 1 & \cdots & 1\end{bmatrix}$（$n$ 个 $1$）。然后，我们发现转移矩阵就是题目中给出的邻接矩阵 $E$。目标矩阵为 $B \times E^K$，答案为目标矩阵的第一行之和。

• S 数位 DP。设 $l$ 为 $n$ 的位数，$s_i$ 为 $n$ 的第 $(l - 1)$ 位到第 $i$ 位之和，$f_{i, j, k}$ 为目前填到第 $i$ 位，位数和 $\mod d$ 的结果，$sum_{i, j} = \sum_{k = 0}^9 f_{i, j, k}$。转移有 $f_{i, j, k} = sum_{i - 1, ((j - k) \bmod d + d) \bmod d}$。

  答案可以分成两类统计：位数小于 $l$ 的，和位数等于 $l$ 的。

  第一类为 $\sum_{i = 0}^{l - 2} sum_{i, 0} - f_{i, 0, 0}$（前导 $0$ 的情况不能算）。

  第二类为 $\left(\sum_{i = 0}^{l - 1}\sum_{k = [i = l - 1]}^{\frac{n}{10^i} \bmod 10 - 1} f_{i, x, k}\right) + [s_0 = 0]$。其中 $x \in [0, d]$ 且 $x + s_{i + 1} \equiv 0 \pmod d$。意思已经很明显了，第 $l - 1$ 位到第 $i + 1$ 位都与 $n$ 相等，数位和已经确定，现在要求的填法使得第 $i$ 位小于 $n$，并且数位和与已经确定的部分之和模 $d$ 为 $0$，至于 $[s_0 = 0]$ 就是看 $n$ 是否符合要求。

  这样统计答案可以做到不重不漏。

• T 前缀和优化 DP。设 $f_{i, j}$ 为前 $i$ 个位置填了互不相同的 $i$ 个数，其中最后一个数在其中的排名为 $j$。可以列出状态转移方程 $f_{i, j} = \begin{cases}\sum_{k = 1}^{j - 1} f_{i - 1, k} & op_{i - 1} = \texttt{"<"} \\ \sum_{k = j}^i f_{i - 1, k} & op_{i - 1} = \texttt{">"}\end{cases}$。使用前缀和优化即可。

• U 状压 + 枚举子集。首先 $O(n^22^n)$ 预处理出 $\operatorname{score}(s)$ 为将 $s$ 内的兔子分到一组的得分。然后设 $f_i$ 为兔子选择状态为 $i$ 时的最大得分。（选择的兔子分成了若干组）转移为 $f_i = \max_{j \in i}\{f_{i - j} + \operatorname{score}(s)\}$。总时间复杂度为 $O(n^22^n + 3^n)$。

• V 换根 DP。设 $f_u$ 为 $u$ 节点染色，以 $u$ 为根的子树的方案数，$g_u$ 为 $u$ 节点涂色，以 $u$ 为根的剩余部分方案数，那么 $u$ 节点的答案就是 $f_u \times g_u$。有转移 $f_u = \prod_{v \in \operatorname{son}(u)} f_v + 1$。

  接下来我们考虑一次换根求出 $g$。首先，$g_1 = 1$。然后，$g_v = \left(g_u \times \prod_{p \in \operatorname{son}(p) \& p \not=v} f_p\right) + 1$。如果我们暴力枚举 $p$，时间复杂度会被菊花图卡成 $O(n^2)$。我们可以预处理出 $f_v$ 的前缀积和后缀积，就可以 $O(1)$ 算出 $\prod$ 部分了。

• W 线段树优化 DP。设 $f_j$ 为最后一个 $1$ 在 $j$ 位置的最大得分。由于贡献不太好算，所以我们考虑在每一个区间的右端点处加上这个区间的贡献。得出转移 $f_{i} = \max_{j = 0}^{i - 1}\{f_j\}$，$f_j \to f_j + \sum_{r_k = i \& l_k \le j} a_k$ 第一个转移是个区间最值问题，第二个转移是个区间加，用线段树维护即可。

• X 排序确定 DP 顺序。可以用邻项交换法证明，以 $s_i + w_i$ 小的块应该放在 $s_i + w_i$ 大的块上面。排序后，设 $f_{i, j}$ 为用前 $i$ 个方块建出的塔重量为 $j$ 时塔的最大价值，有转移 $f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - w_i} + v_i) \ (w_i \le j \le s_i + w_i)$。

• Y 因为白格子数量巨大，而黑格子最多只有 $3 \times 10^3$ 个，应该思考按照黑格子计数的方式。

  首先将黑格子按照 $x$，$y$ 排序，然后设 $f_i$ 为从 $(1, 1)$ 走到第 $i$ 个黑格子，且中途不经过其他黑格子的方案数。从 $(1, 1)$ 走到 $(x, y)$ 的方案数显然是 $C_{x + y - 2}^{x - 1}$（或 $C_{x + y - 2}^{y - 1}$），我们可以用它减去至少经过一个黑格子的方案，就得到了 $f_i$。显然可以枚举经过的第一个黑格子，由于经过的第一个黑格子不同，这两条路线就不同，所以可以做到计数不重复。

• Z 听说是斜率优化，我不会（