菜王的 blog

题单

题意

link

有 $n$ 个人和 $m$ 对敌对关系，每一个人有一个条件区间 $[l_i, r_i]$。

现在要在这 $n$ 个人中选若干个人。定义一个合法的选择集合 $s$，$\forall i \in s (l_i \le |s| \le r_i)$，且 $\forall i, j \in s$ 有 $i, j$ 互不敌对。

求有多少种合法的选择，答案对 $998244353$ 取模。

题解

如果没有敌对关系，那么预处理出 $c_i = \sum_{j = 1}^n [l_j \le i \le r_j]$，选取 $x$ 人的方案数就为 $C_{c_x}^x$。

如果有敌对关系，我们考虑用容斥原理。设 $f_i$ 为敌对关系集合 $i$ 里的人全部被选中的方案数，设 $s$ 为所有敌对关系的集合，那么答案为 $\sum_{t \in s} (-1)^{|t|} f_t$。再设与集合 $t$ 对应的集合 $u$ 为 $t$ 中所有敌对关系所包含的人的集合，则 $f_t = \sum_{x = L}^R C_{c_x - |u|}^{x - |u|}$。

预处理出 $C$ 的前缀和即可 $O(nm + 2^m)$ 解决问题。

题意

link

给出一个数列 $a$，请你找出所有的 $x$，满足能在 $a$ 中找到一个异或和为 $x$ 的单调上升子序列。

题解

设 $w$ 为值域。

可以设 $f_{j, k}$ 为是否存在结尾 $\le j$ 且异或值等于 $k$ 的上升子序列。

然后如果 $f_{a_i, k} = 1$，就将所有满足 $a_i < j < w$ 的 $f_{j, k \oplus a_i}$ 更新为 $1$。

我们可以不维护 $f$ 数组，改为维护 $w$ 个 vector，第 $j$ 个 vector 里存所有满足 $f_{j, k} = 1$ 的 $k$，由于对于每一个 $a_i$，$k$ 只需要枚举一遍，所以遇到每一个 $a_i$ 可以将所有的 $k$ 都枚举了，然后清空第 $a_i$ 个 vector，时间复杂度为 $O(n + w^3)$。

然后我们发现，对于相同的 $k \oplus a_i$，我们不需要重复更新，维护一个 $mx_k$ 记录 $f_{j, k}$ 没被更新过的最大 $j$ 就能确保不被重复更新。

时间复杂度为 $O(n + w^2)$。

题意

link

有 $n$ 名同学要乘坐摆渡车从人大附中前往人民大学，第 $i$ 位同学在第 $t_i$ 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发，把车上的同学送到人民大学，再回到人大附中（去接其他同学），这样往返一趟总共花费 $m$ 分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

如果能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

题解

经典 DP 好题！

预处理 $[0, i]$ 时间内出发的人数 $cnt_i$， $[0, i]$ 时间内出发的人的出发时间总和 $sum_i$。

我们可以想到一个 $O(t^2)$ 的做法：设 $f_i$ 为摆渡车最后一次出发时间为 $i$，所能达到的最小等候时间。

状态转移方程为 $f_i = \min_{j \le i - m}(f_j + (cnt_i - cnt_j) \times i - (sum_i - sum_j))$。

这个转移方程显然可以斜率优化，但是没必要。

1. 考虑去除无效转移。

上述状态转移方程可以优化为 $f_i = \min_{i - 2m + 1 \le j \le i - m}(f_j + (cnt_i - cnt_j) \times i - (sum_i - sum_j))$。

为什么呢？

显然，多出车答案肯定不会变劣。所以，当 $[j, i)$ 一段长度大于等于 $2m$ 时，我们可以再出一次车。

时间复杂度为 $O(tm)$。

2. 考虑去除无效状态。

我们考虑，如果一个 $f_i$ 满足 $cnt_i = cnt_{i - m}$（即 $(i - m, i]$ 中没有任何人），则这个 $f_i$ 没用，相当于 $f_{i - m}$。因为在 $i$ 出发一次是没有意义的。

可以证明，所有有用的 $i$ 最多有 $nm$ 个，所以时间复杂度为 $O(nm^2 + t)$，可以通过。

题意

link

给出一个长度为 $n$ 的序列 $a$，求先序遍历为 $a$ 的树棵数。

保证 $a_1 = 1$。

题解

设 $f_{l, r}$ 为先序遍历为 $a_{l \sim r}$ 的树棵数。

设 $g_{l, r}$ 为先序遍历为 $a_{l \sim r}$，且使 $a_{r + 1}$ 成为 $a_l$ 的儿子后，先序遍历为 $a_{l \sim r + 1}$ 的数棵数（$r < n$）。

可以列出转移方程：

$f_{l, r} = \sum_{l < i \le r} g_{l, i - 1} \times f_{i, r}$

$g_{l, r} = \sum_{l < i \le r \&\& a_i < a_{r + 1}} g_{l, i - 1} \times f_{i, r}$

$f$ 的转移方程解释：

• 把先序遍历为 $a_{i + 1 \sim r}$ 树接在先序遍历为 $a_{l \sim i}$ 的树上，成为节点 $a_l$ 的一棵子树。

• 因为接上先序遍历为 $a_{i + 1 \sim r}$ 树后先序遍历顺序不能变，所以先序遍历为 $a_{l \sim i}$ 的树的方案数为 $g_{l, i}$。

• 先序遍历为 $a_{i + 1 \sim r}$ 树的方案数为 $f_{i + 1, r}$。

• 两个部分互不关联，所以方案数为 $g_{l, i} \times f_{i + 1, r}$。

$g$ 的转移方程与 $f$ 的转移方程类似，但是因为 $g$ 的定义，$a_i < a_{r + 1}$ 时才能转移，否则先序遍历会先遍历到 $a_{r + 1}$，与定义不符。

时间复杂度为 $O(n^3)$。

题意

link

给你一个序列，请问有多少个子序列按位与和为 $0$。

题解

令值域为 $m$，$k$ 为 $\lfloor\log_2 m\rfloor$。

设 $f_i$ 为选出一个子序列使得按位与和 $x$ 满足 $x \& i = i$ 的方案数。

根据容斥原理，答案显然是：

$\sum_{i = 0}^m (-1)^{\operatorname{popcnt}(i)} f_i$

关键在于 $f_i$ 怎么求。

设 $g_{j, i}$ 为 $x \& i = i$，且 $x \oplus i < 2^j$ 的 $x$ 个数（即 $x$ 只有前 $j$ 位可能与 $i$ 不同），$g_i = g_{k, i}$，则 $f_i = 2^{g_i} - 1$。

$g_{j, i}$ 其实是一个 DP，阶段为 $j$。可以轻松写出转移方程：

$\begin{cases} i \& 2^j = 0 & g_{j, i} = g_{j - 1, i} + g_{j - 1, i + 2^j}\\ \mathrm{otherwise} & g_{j, i} = g_{j - 1, i}\\ \end{cases}$

$\operatorname{popcnt}$，容斥原理 和 $g$ 可以在 $O(m \log m)$ 内求出，读入与预处理二的次幂可以 $O(n)$ 完成，总时间复杂度为 $O(n + m \log m)$。

题意

link

有一个多重集 $S$，$S$ 由 $1 \sim n$ 的整数组成，有 $a_1$ 个 $1$，$a_2$ 个 $2$，……，$a_n$ 个 $n$。

现在从 $S$ 里选出 $m$ 个元素组成多重集 $T$，请问能组成多少个不同的 $T$？

题解

经典的插板法 + 容斥。

我们先不考虑数量的限制，解决问题的简化版：

有一个多重集 $S$，$S$ 由 $1 \sim n$ 的整数组成，有 $\inf$ 个 $1$，$\inf$ 个 $2$，……，$\inf$ 个 $n$。

现在从 $S$ 里选出 $m$ 个元素组成多重集 $T$，请问能组成多少个不同的 $T$？

这个问题相当于在 $m$ 个小球之间插 $n - 1$ 块板，两个球之间可以插多块板。这样一插，$m$ 个小球就被分成了 $n$ 段，第一段全部为 $1$，第二段全部为 $2$，以此类推。方案数为 $C_{m + n - 1}^{n - 1}$。

由于满足要求的情况不太好算，我们运用容斥原理，算不满足要求的情况。还是那个公式：

$f(U) = \sum_{V \in U} (-1)^{|V|} f'(V)$

其中，$U$ 是要求的集合，$f(U)$ 为满足 $U$ 内所有条件的方案数，$f'(U)$ 为 $U$ 内所有条件都不满足的方案数。

$f'(U)$ 其实就相当于这个问题：

有一个多重集 $S$，$S$ 由 $1 \sim n$ 的整数组成，有 $\inf$ 个 $1$，$\inf$ 个 $2$，……，$\inf$ 个 $n$。

现在从 $S$ 里选出 $m$ 个元素组成多重集 $T$，且 $\forall i \in U$，$T$ 里至少有 $a_i + 1$ 个 $i$，请问能组成多少个不同的 $T$？

这个问题也很好解决，设 $cnt$ 为 $\sum_{p \in U} a_p + 1$，然后这个问题就相当于限制了 $cnt$ 个数，剩下的数还是任选，所以有 $C_{m + n - cnt - 1}^{n - 1}$ 种方案。

最后一个问题：组合数怎么求？根据组合数的定义，有

$C_n^m = \dfrac{n!}{(n - m)!m!}$

$n!$ 和 $(n - m)!$ 可以抵消，变为

$C_n^m = \dfrac{\prod_{i = n - m + 1}^n i}{m!}$

然后就可以 $O(m)$ 求组合数了。

因为涉及到的组合数 $n$ 很大 $m$ 很小，所以这样求不会超时，反而比预处理阶乘要快。

题意

link

将 $n$ 对情侣排成一排，请问有多少种方案使得恰好存在 $k$ 个 $i$，使得在第 $2i - 1$ 个位置上的人与在第 $2i$ 个位置上的人是情侣？

题解

有趣的递推。

设 $g(i)$ 为 $i$ 对情侣存在 $0$ 个位置满足条件的方案数，那么答案即为：

$ans = C_n^k \times A_n^k \times 2^k \times g(n - k)$

我们考虑递推求出 $g$。

考虑前两个位置的情况，有男男、女女、男女、女男四种情况。

假设前两个位置都是 gay 男方（方案数为 $i(i - 1)$），然后考虑他们的配偶的位置：

1. 配对

   有 $i - 1$ 个配对的位置，且两个女方位置可以交换，方案数为 $2(i - 1)g(i - 2)$；

2. 不配对

   我们可以把她们也当作一对情侣，方案数为 $g(i - 1)$。

其他的情况方案数都是一致的。

至此，我们得到了递推公式：

$g(i) = 4i(i - 1)(2(i - 1)g(i - 2) + g(i - 1))$

题意

link

定义 $f(p)$ 为 $p$ 的 $|p|$ 个前缀 $\gcd$ 中不同的数的个数（$p$ 是一个排列）。

你需要求满足 $f(a) = \max f(p)$ 的 $1 \sim n$ 的排列 $a$ 的个数对 $10^9+7$ 取模的值，其中 $p$ 取遍 $1 \sim n$ 的所有排列。

题解

先得到结论后 DP。

我们考虑 $\gcd$ 是如何变化的。

对于一个排列，前 $i$ 个数的 $\gcd$ 变化到前 $i + 1$ 个数的 $\gcd$，要么不变，要么至少减半。

题目要求的是变化次数最大，所以我们尽可能让每次变化都只减半，最多可以减半 $\lfloor \log_2 n \rfloor$ 次，所以 $\max f(p) = \lfloor \log_2 n \rfloor$。以下设 $m$ 为 $\max f(p)$。

那么排列的第一个数是不是一定就是 $2^m$ 呢？答案是否定的。

我们尝试着把 $2^m$ 中的一个因子 $2$ 换成其他数。

我们发现，这个数只能是 $3$。因为如果这个数大于等于 $4$，那么 $m$ 就不是最大的了。

所以我们得到了一个结论：排列的第一个数一定可以被写成 $2^x3^y$ 的形式，且 $y \in \{0, 1\}$。

得到了这个结论之后，我们就可以直接 DP 了。设 $f_{i, x, y}$ 为决定了前 $i$ 个数，$\gcd$ 为 $2^x3^y$ 的方案数。

考虑第 $i$ 个数，分类讨论转移：

1. $\gcd$ 不变。此时 $f_{i, x, y} = (cnt(2^x3^y) - i + 1)f_{i - 1, x, y}$。
2. $\gcd$ 除以二。此时 $f_{i, x, y} = (cnt(2^x3^y) - cnt(2^{x + 1}3^y))f_{i - 1, x + 1, y}$。
3. $\gcd$ 除以三。此时 $f_{i, x, y} = (cnt(2^x3^y) - cnt(2^x3^{y + 1}))f_{i - 1, x, y + 1}$。

其中 $cnt(i)$ 为 $1 \sim n$ 中为 $i$ 倍数的数个数。（其实就是 $\lfloor\frac ni\rfloor$）

$x$ 是 $\log n$ 级别的，时间复杂度为 $O(n \log n)$。

题意

link

有 $n$ 个物品和一个正整数 $m$，每个物品都有自己的重量且只能使用一次，对于所有 $i \in [1, n]$ 且 $j \in [1, m]$ 请你求出不用第 $i$ 个物品只用其他物品凑出重量 $j$ 的方案数。

题解

退背包，一个背包的深层应用，加深了我对背包的理解。

暴力跑背包是 $O(n^2m)$ 的，不够优。

我们首先跑一遍完整的背包，然后考虑设 $g_{i, j}$ 为不用第 $i$ 个物品只用其他物品凑出重量 $j$ 的方案数。

考虑容斥转移，$g_{i, j} = f_{n, j} - g_{i, j - w_i}$，即凑出 $j$ 的所有方案数减去使用了 $i$ 凑出 $j$ 的方案数。

但是需要注意，$g_{i, j} = f_{n, j} - f_{i, j - w_i}$ 是错的，因为 $f_{i, j - w_i}$ 里可能也选了 $i$。

时间复杂度为 $O(nm)$，与 01 背包一致。

题意

link

有 $a$ 个 $1$，$b$ 个 $2$，$c$ 个 $3$，你要把这些数选出一些分成 $n$ 组，满足：

• 每组至少有一个数；

• 每组里没有相同的数；

• 组和组是有区别的，比如 $\{1\}, \{2\}$ 和 $\{2\}, \{1\}$ 是不同的两种方案；

• 顺序是没有影响的，比如 $\{1, 2\}$ 和 $\{2, 1\}$ 是同一种方案；

• 相同的元素是等价的。

题解

根据容斥原理，我们可以推出以下式子：

$ans = \sum_{m = 0}^n (-1)^{n - m} \binom{n}{m} \left(\sum_{i = 0}^{\min(a, m)} \binom mi\right)\left(\sum_{j = 0}^{\min(b, m)} \binom mj\right)\left(\sum_{k = 0}^{\min(c, m)} \binom mk\right)$

然后发现这个式子可以 $O(n^2)$ 计算，但是很难化简，怎么办？

我们考虑设 $f_m(n)$ 为 $\sum_{i = 0}^{\min(n, m)} \binom ni$，然后考虑从 $f_m(n)$ 递推 $f_m(n + 1)$。

当 $n + 1 \le m$，也就是 $n < m$ 时，有 $f_m(n + 1) = 2^{n + 1}$，即 $f_m(n + 1) = 2f_m(n)$。

否则，当 $n \ge m$ 时，我们考虑用网格图分析问题。（这也是这道题的精华部分）

考虑这样一张网格图：

$f_m(n)$ 就相当于从 $(0, 0)$ 出发向上走或向右走走到橙色点的方案数，$f_m(n + 1)$ 就相当于从 $(0, 0)$ 出发向上走或向右走走到蓝色点的方案数。

我们考虑走到橙色点之后，向上走一步或向右走一步都能到达蓝点，只有一个例外——在 $(m, n - m)$ 且向右走的情况。

所以 $f_m(n + 1) = 2f_m(n) - \binom nm$。

至此，我们推出了 $f_m(n)$ 的递推式，最开始的式子可以简化为：

$ans = \sum_{m = 0}^n (-1)^{n - m} \binom{n}{m} f_a(m)f_b(m)f_c(m)$

$f_a(m), f_b(m), f_c(m)$ 都可以 $O(n)$ 递推，时间复杂度为 $O(n)$。

题意

link

给出 $n, m$ 以及长度为 $n$ 的数列 $g$，构造一个长度为 $n$ 的数列 $a$，满足 $\sum_{i = 1}^n a_i = m$，最小化 $\sum_{i = 1}^n \sum_{j = 1}^n g_i[a_j > a_i]$。

题解

有启发性的 DP。

如果我们想要按照 $1 \sim n$ 的顺序去分配 $a_i$，会导致每个孩子的怒气值不断变化。

显然，$g_i$ 越大的孩子应该分配越多的饼干。我们将 $g_i$ 从大到小排序，并规定分配的饼干单调不升。可以推出状态：$f_{i, j}$ 为给前 $i$ 个孩子分配 $j$ 个饼干的最小怒气值。转移可以考虑给第 $i$ 个孩子分配饼干的个数 $a_i$。

如果 $a_i > 1$，就相当于给前 $i$ 个孩子分配 $j - i$ 个饼干，每人少要一块。如果 $a_i = 1$，枚举 $i$ 之前有多少个 $a_i = 1$ 直接计算即可。

可以推出转移方程：$f_{i, j} = \min(f_{i, j - i}, f_{k, j - (i - k)} + k \times \sum_{l = k + 1}^i g_l (0 \le k < i))$，时间复杂度为 $O(n^2m)$。

题意

link

给定 $n$ 种硬币，其中第 $i$ 种硬币的面值为 $a_i$，共有 $c_i$ 个。

求 $1 \sim m$ 之间能被拼成的面值有多少个。

题解

为数不多的背包好题。我们不妨思考一个问题：前 $i$ 种硬币能拼出面值 $j$ 需要满足什么条件？可以得出这样的结果：

1. 用前 $i - 1$ 种硬币就能拼出 $j$。

2. 用前 $i - 1$ 种硬币可以拼出面值 $x$，且 $x + k \times a_i = j(1 \le k \le c_i)$。

由于我们只关注“可行性”，所以我们不关心 $x$ 是如何拼成的，只关心拼成 $x$ 使用的最少 $a_i$，于是我们可以对于每一种硬币记录一个 $use_j$ 来表示使用前 $i$ 枚硬币拼成面值 $j$ 用的最小 $a_i$ 个数，并贪心地尽量满足条件一。

在完全背包的基础上使用 $use$ 数组限制一下次数就能做到 $O(nm)$。

题意

link

给出一棵树的 DFS 序，求可能的树方案数。

题解

观察所给出的序列，每一棵子树都对应着序列里的一个区间，所以我们可以设区间 $[l, r]$ 的方案数为 $f_{l, r}$。

那如何转移呢？如果我们枚举这个区间被分成了多少区间，再枚举每个分界点，时间复杂度会爆炸。

我们可以枚举一个分界点 $k$，$[l + 1, k - 1]$ 对应第一棵子树的位置，而 $[k, r]$ 对应剩下的部分（这也是一个子问题）。两个部分不相关，满足乘法原理，转移时乘起来即可。

题意

link

有一个长度为 $n$ 的数列 $a$，每一次操作可以从 $a$ 中删除一个满足 $a_l = a_{l + 1} = a_{l + 2} = \cdots = a_r$ 的区间 $[l, r]$，并获得 $(r - l + 1)^2$ 的得分（然后 $a$ 会保持连续）。最大化把序列删空的得分。

题解

有点意思的区间 DP。首先将相同颜色的缩成一块，颜色为 $a_i$，数量为 $b_i$。

单纯设 $f_{l, r}$ 为删除 $[l, r]$ 的最大得分是不行的，无法转移。所以，我们设 $f_{l, r, i}$ 为 $r$ 后还有 $i$ 块与 $r$ 颜色相同的块，删除 $[l, r]$ 以及 $r$ 后 $i$ 块的最大得分。每个状态有两种转移：

1. $f_{l, r, i} = f_{l, r - 1, 0} + f_{r, r, i}$，这意味着直接把最后一段删除。

2. $f_{l, r, i} = \max_{l \le k < r \& a_k = a_r}\{f_{l, k, b_r + i} + f_{k + 1, r - 1, 0}\}$，这意味着找到一个颜色与右端点相同的 $k$，并删掉 $[k + 1, r - 1]$，让右边的块合并到一起。

特别的，$f_{l, l, i} = (b_l + i)^2$，时间复杂度为 $O(n^4)$，常数优秀。

题意

link

给定一棵树，在树上选三个点，要求这三个点两两距离相等，求方案数。

题解

神仙树形 DP。

有一个性质：如果树上三个点相等，那么其中深度较深的两个点的 LCA 到它们三个点距离相等。于是，我们可以枚举这个 LCA 变成根并选择三个深度相同且在不同子树里的点。为什么要在不同子树里呢？因为要保证他们的 LCA 还是根。

对于每一个根节点，我们可以设 $f_{i, j}$ 为在已经遍历过的子树内选出 $j$ 个深度为 $i$ 的点的方案数，$cnt_i$ 为当前子树里深度为 $i$ 的点的个数。对于每一个深度 $i$，使 $ans \to ans + f_{i, 2} \times cnt_i$，$f_{i, 2} \to f_{i, 2} + f_{i, 1} \times cnt_i$，$f_{i, 1} \to f_{i, 1} + cnt_i$。

$ans$ 需要开 long long，时间复杂度为 $O(n^2)$。

题意

link

给一棵 $n$ 个点的树，边有长度。

有 $k$ 个人分布在 $k$ 个不同的点，要集中到一个点举行聚会。

聚会结束后需要一辆车从举行聚会的这点出发，把这 $k$ 个人分别送回去。

请你回答，对于 $i=1 \sim n$ ，如果在第 $i$ 个点举行聚会，司机最少需要多少时间把 $k$ 个人都送回家。

题解

神仙换根 DP + 毒瘤分类讨论。首先 DP 出 $f_u$ 代表从 $u$ 出发将 $u$ 子树内的人都送回家再回到 $u$ 的距离，$len_{u, 0/1}$ 代表以 $u$ 为起点在 $u$ 子树内最长链 / 次长链长度，$maxs_u$ 代表 $u$ 子树内最长链所在的子树，$sump_u$ 代表以 $u$ 为起点 $u$ 子树内客人家的个数。

然后就是换根了。设 $g_u$ 为从 $u$ 出发将所有人都送回家再回到 $u$ 的距离，$len_{u, 0/1}$ 为以 $u$ 为起点整棵树内最长链 / 次长链长度，$maxs_u$ 代表以 $u$ 为起点整棵树内子树内最长链所在的子树。

分类讨论如何转移：

1. $v$ 子树内没有家。此时 $g_v = g_u + w \times 2$，$len_{v, 0} = len_{u, 0} + w$。

2. 所有的家都在 $v$ 子树内。此时 $g_v = f_v$，$len_{u, 0}$ 与 $len_{u, 1}$ 不变。

3. 其他情况。此时 $g_v = g_u$，我们需要讨论最长链的更新。

   1. 如果 $maxs_u \not= v$，那么 $u$ 的最长链可以更新 $v$ 的最长链和次长链。

   2. 无论如何 $u$ 的次长链都可以更新 $v$ 的最长链和次长链。

最后，每个节点 $u$ 的答案为 $g_u - len_{u, 0}$。

题意

link

有一个 $n$ 个点的图，最初没有任何边，你需要选择一个点为源点。

给出 $m$ 条可以添加的边。

添加一条边的代价是 $w \times dis$，其中 $w$ 代表这条道路的长度，$dis$ 代表从源点到这条道路起点所经过的节点数量（包括源点和这条道路起点） 。

请你编写程序选定起点和之后添加的边，使得使图连接的总代价最小。

题解

我们想到，可以设 $f_{i, j}$ 为前 $i$ 层，节点的打通情况为 $j$ 时的最小花费。其中 $j$ 是一个三进制整数，它的第 $u - 1$ 位为 $0$ 时代表节点 $u$ 没被打通，为 $1$ 时代表节点 $u$ 在第 $i$ 层之前被打通了，为 $2$ 时代表节点 $u$ 是在第 $i$ 层被打通的。转移有三种：

1. 不再从第 $i$ 层打通道路，转移为 $f_{i + 1, s} = \min(f_{i + 1, s}, f_{i, j})$，其中 $s$ 为 $j$ 将每一个为 $2$ 的三进制位换成 $1$ 得到的新数字，这意味着在第 $i$ 层打通的节点在第 $i + 1$ 层可以用来打通别的节点。

2. 从 $j$ 最低的 $1$ 所对应的节点 $u$ 进行拓展。枚举所有没被打通且与 $u$ 连接的 $v$，转移为 $f_{i, j + 2 \times 3^{v - 1}} = \min(f_{i, j + 2 \times 3^{v - 1}}, f_{i, j} + e(u, v))$。

3. 不从 $j$ 最低的 $1$ 所对应的节点 $u$ 进行拓展。转移为 $f_{i, j + 3^{u - 1}} = \min(f_{i, j + 3^{u - 1}}, f_{i, j})$。将 $u$ 所代表的位变成 $2$ 可以起到避免拓展的作用。

在此题中，$i$ 维和 $j$ 维都是阶段，相同的 $i$ 中 $j$ 只会从小到大转移，所以没有后效性。

需要注意的是，三进制状压 DP 不能使用位运算，只能使用乘法，除法，取模等低效运算，实现时注意降低常数。

题意

link

一个 $n \times m$ 的棋盘，其中有 $k$ 个黑格子，其它的都是白格子。请你求出从 $(1, 1)$ 只经过白格子走到 $(n, m)$ 的方案数。

题解

因为白格子数量巨大，而黑格子最多只有 $2 \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$。显然可以枚举经过的第一个黑格子，由于经过的第一个黑格子不同，这两条路线就不同，所以可以做到计数不重复。

于是 $f_i = C_{x_i + y_i - 2}^{x_i - 1} - \sum_{j = 1}^{i - 1} [x_j \le x_i \& y_j \le y_i]f_j \times C_{x_i - x_j + y_i - y_j}$。我们可以设第 $n + 1$ 个黑格子为 $(H, W)$，于是答案就是 $f_{n + 1}$。

题意

link

给一个只包含 $\texttt{"K"}, \texttt{"E"}, \texttt{"Y"}$ 的字符串 $s$。

请问至多交换 $k$ 次 $s$ 的相邻字符能形成多少个不同的字符串？

题解

首先将 $K$ 与 $\dfrac{n \times (n - 1)}{2}$ 取最小值。

然后设 $f_{i, j, k, x}$ 为长度为 $i$，包含 $j$ 个 $\texttt{"K"}$，$k$ 个 $\texttt{"E"}$，$i - j - k$ 个 $\texttt{"Y"}$，需要至少在字符串 $S$ 中执行 $x$ 次操作才能与字符串 $S$ 的前 $i$ 位相等的字符串 $T$ 个数，答案为 $\sum_{i = 0}^K f_{n, cnt1, cnt2, i}$。

题意

link

有一个 $n \times m$ 的网格，每个格子里面有一个 $1 \sim 9$ 的数。最初你站在其中一个格子上。

你需要移动 $2k$ 次，第奇 / 偶数次移动可以移到与你当前位置同一行 / 列的位置。

每次移动后你需要把你所在的网格上的数字写下来。

最后你把你写下来的 $2k$ 个数位按顺序组成一个数，这就是你的分数。

请你求出所有情况下的分数之和。

题解

首先设 $f_{i, j, 0 / 1}$ 为第 $i$ 轮，刚刚移到同一行 / 列的格子里，结束在第 $j$ 列 / 行的方案数，但是，这样会重复计数。

设 $f_{i, s, 0 / 1}$ 为第 $i$ 轮，刚刚移到同一行 / 列的格子里，可能结束在集合 $s$ 中的列 / 行的方案数，可以做到不重不漏的计算每种状态。设行集合为 $R$，答案为 $\sum_{s \subseteq R} f_{n, s, 1}$，转移不多提。

题意

link1

求 $n$ 个节点的有标号简单无向连通图个数。

link2

求 $n$ 个节点，不超过 $m$ 条割边的有标号简单无向连通图个数。

题解

显然，$n$ 个节点的无向连通图个数等于 $n$ 个节点的无向图个数与 $n$ 个节点的无向不连通图个数之差，且我们考虑计算后者。

$n$ 个节点的无向图个数显然是 $2^{n(n - 1)/2}$。因为，每条边可以选择选或不选，且一共有 $n(n - 1) / 2$ 条边。

我们可以设 $h_i$ 为 $i$ 个节点的无向连通图个数，那么 $i$ 个节点的无向不连通图个数为 $\sum_{j = 1}^{i - 1} h_j \times C_{i - 1}^{j - 1} \times 2^{i - j(i - j - 1) / 2}$。

为什么是这样的呢？一个无向不连通图可以划分成若干个联通块，于是我们枚举 $1$ 号节点所在的连通块大小。

设它的大小为 $j$，除了 $1$ 号节点外，我们可以在剩下 $i - 1$ 个节点中选出 $j - 1$ 个节点组成 $j$ 个节点的无向连通图，数量为 $h_j \times C_{i - 1}^{j - 1}$；而剩下 $i - j$ 个节点组成任意无向图，数量为 $2^{i - j(i - j - 1) / 2}$。那 $h_i$ 就等于 $2^{i(i - 1) / 2} - \sum_{j = 1}^{i - 1} f_j \times C_{i - 1}^{j - 1} \times 2^{i - j(i - j - 1) / 2}$。

时间复杂度为 $O(n^2)$。

---

设 $f_{i, j}$ 为 $i$ 个节点组成 $j$ 条割边的无向连通图的方案数，$g_{i, j, k}$ 为 $i$ 个节点组成 $j$ 条割边，$k$ 个连通块，且这 $k$ 个连通块都连接到另一个强连通分量上的方案数。

转移如下：

$f_{i, j} = \sum_{k = 1}^{i - 1}f_{k, 0} \times C_{i - 1}^{k - 1} \times \sum_{x = 1}^{\min(i - k, j)} g_{i - k, j - x, x} \times k^x$

$g_{i, j, k} = \sum_{p = 1}^i\sum_{q = 0}^k f_{p, q} \times C_{i - 1}^{k - 1} \times p \times g_{i - p, j - q, k - 1}$

预处理组合数和 $k^x$，时间复杂度为 $O(n^5)$。

题意

link

有一个长度为 $n$ 的序列 $a$，要求把该序列分成若干段，每段中所有数的和不超过 $m$，最小化每段中所有数的最大值之和。

题解

单调队列 + 二叉堆优化 DP。

我们可以设 $f_i$ 为将前 $i$ 个数分为若干段的最小代价，然后可以直接 $O(n^2)$ 暴力 DP，思考如何优化。

有一个结论，若 $f_j$ 可以成为 $f_i$ 的最优决策，那么 $a_j = \max_{k = j}^i a_k$ 与 $\sum_{k = j}^i a_k > m$（$j$ 是满足 $\sum_{k = j}^i a_k \le m$ 最小的 $j$）中必定有一个成立。

证明

反证法。

首先，$f$ 数组具有单调性（如果 $j < i$，$f_j \le f_i$）。

然后，如果两个条件都不满足，肯定满足 $\max_{k = j}^i \{a_k\} = \max_{k = j + 1}^i \{a_k\}$。因为 $f$ 数组具有单调性，所以 $f_{j - 1} + \max_{k = j}^i\{a_k\} \le f_j + \max_{k = j + 1}^i \{a_k\}$，结论成立。

于是我们可以维护一个 $j$ 单调递增，$a_j$ 单调递减的单调队列，队列里的元素才可能成为最优决策。

但是队列里的答案不满足单调性，所以我们可以再使用一个二叉堆维护队列里答案的最小值，时间复杂度为 $O(n \log n)$。

题意

link

将一个序列划分成若干个连续非空子序列的得分是这几个子序列的极差之积，请求出所有划分方法的得分总和。

题解

设 $f_i$ 为划分前 $i$ 个元素形成的子序列的得分总和，那么我们可以列出转移方程：

$f_0 = 1$

$f_i = \sum_{j = 0}^{i - 1} f_j \times (\max_{j < k \le i} a_k - \min_{j < k \le i} a_k)$

然后可以把 $\min$ 和 $\max$ 分开考虑：

$\begin{aligned} f_i &= \sum_{j = 0}^{i - 1} f_j \times \max_{j < k \le i} a_k - f_j \times \min_{j < k \le i} a_k\\ &= \sum_{j = 0}^{i - 1} f_j \times \max_{j < k \le i} a_k - \sum_{j = 0}^{i - 1} f_j \times \min_{j < k \le i} a_k \end{aligned}$

$\min$ 和 $\max$ 是类似的，我们只需考虑其中一个，这里考虑 $\max$。

考虑维护一个元素单调递减的单调栈来维护 $\max$ 变化的位置，用前缀和辅助转移即可。

$\min$ 同理维护一个元素单调递增的单调栈即可。

题意

link

给定平面上的 $n$ 个点的坐标 $(x_i, y_i)$，其中没有两点有相同的坐标。（以下提到的距离都指曼哈顿距离）

现用 $n$ 种颜色对这些点进行染色，求满足以下条件的方案数：

• 每种相同颜色的点两两间距离相等（本条及以下提到的距离都指曼哈顿距离）

• 每个点到具有不同颜色的点的距离大于与其颜色相同的其他点（若存在）的距离。

题解

很妙的结论 DP。

首先有一个结论：可以与一个点染相同的颜色的点一定是离这个点最近的所有点，证明简单不讲。

然后我们拓展这个结论，一些点的颜色都可以染成相同的，当且仅当这些点互为最近点，且不存在一个点出现”有多个最近点，一些染成了与这个点相同的，一些没有“的情况。

所以我们可以将这些点按要求分组，可以染成相同色的点分在，处理出每组的大小，然后设 $f_{i, j}$ 为用 $j$ 种颜色染 $i$ 前 $i$ 组的方案数（颜色不考虑顺序），直接转移即可。

如果有 $m$ 组，答案为 $\sum_{i = 1}^n f_{m, i} \times A_m^i$。

时间复杂度为 $O(n^2)$。

题意

link

给一个 $n \times n$ 的网格，每个格子里都有一个颜色，定义只向下或向右走形成的路径为简单路径，请求出起点和终点颜色一样的简单路径条数。

题解

数数题套根号分治。

我们考虑对每个颜色出现的次数根号分治，令阈值为 $lim$。

1. 对于出现次数 $\le lim$ 的颜色：

   直接暴力枚举起点和终点，组合数 $O(1)$ 计算答案。

2. 对于出现次数 $> lim$ 的颜色：

   设当前颜色为 $x$，设 $f_{i, j}$ 为从任意一个颜色为 $x$ 的节点出发走到 $(i, j)$ 的方案数，直接 $O(n^2)$ DP 即可。

第一部分时间复杂度为 $O(\frac{n^2}{lim} \times lim^2)$，化简得 $O(n^2lim)$。

第二部分时间复杂度为 $O(\frac{n^2}{lim} \times n^2)$，化简得 $O(\frac{n^4}{lim})$。

$lim$ 取 $n$ 最优，时间复杂度为 $O(n^3)$。

题意

link

对于一个长度为 $n$，值域为 $[1, m]$ 的序列 $a$，定义 $f(a)$ 为一个长度为 $n$ 且每一项都为 $0$ 的序列 $b$ 执行以下操作变成 $a$ 的最小操作次数：

• 选择 $b$ 的一个区间 $[l, r]$ 与一个 $[1, m]$ 的整数 $x$，将 $b[l, r]$ 里每一项与 $x$ 取 $\max$。

给定 $n, m$，请你求出所有长度为 $n$，值域为 $[1, m]$ 的序列 $a$ 的 $f(a)$ 之和 $\bmod 998244353$。

题解

显然，对于 $b$ 每一个元素单独做一次操作，共做 $n$ 次操作即可达到任意一个序列 $a$，所以答案的一个上界是 $n \times m^n$。

然后我们考虑节省操作。发现 $b_i$ 与 $b_j$ 可以一个操作完成，当且仅当 $\max_{k = i + 1}^{j - 1}\{a_k\} \le a_i = a_j$，显然这时我们可以直接对区间 $[i, j]$ 与 $a_i$ 取最大值且不影响别的操作。

相应的，我们考虑相邻两个相等的数 $a_i, a_j$，$b_i$ 与 $b_j$ 可以一个操作完成，节省一次操作，当且仅当 $\max_{k = i + 1}^{j - 1}\{a_k\} < a_i = a_j$。（这里小于号是因为保证了 $a_i$ 和 $a_j$ 是相邻两个相等的数，它们之间不能有别的出现）

现在，节省的操作数可以通过枚举 $i, j$ 简便的计算，用答案上界减去节省的操作数，就可以得出答案柿子：

$n \times m^n - \sum_{i = 1}^n \sum_{j = i + 1}^n m^{n - (j - i + 1)} \sum_{k = 1}^m (m - k)^{j - i - 1}$

可以 $O(n^2 + nm)$ 计算。

题意

link

有一个大小为 $n$ 的可重集 $a$，你可以执行任意次操作，每次操作将一个 $a$ 里的元素 $x$ 换成两个使得 $pq = x$ 的正整数 $p, q$，请你最小化 $\max a - \min a$。

题解

双指针 + DP。

看到极差问题，我们首先想到在值域上跑双指针。然后考虑这样一个 DP：设 $f_{i, j}$ 为 $j$ 这个数拆成若干个数之积之后，钦定每个拆出来的数都 $\ge i$，拆出来最大的数的最小值。

转移是比较好想的，当 $i \mid j$ 且 $i^2 \le j$ 时，$f_{i, j} = \min(f_{i, j}, f_{i, j / i})$（要求 $i^2 \le j$ 是因为要保证 $j / i > i$）。否则，$f_{i, j} = f_{i + 1, j}$，因为 $i$ 无法拆出来。

然后发现 $j$ 可以直接调和级数枚举，$i$ 维可以滚掉，所以 $f$ 的 DP 可以做到 $O(m \ln m)$ 处理。

设双指针的左端点为 $l$，右端点即为 $\max_{i = 1}^n f_{l, a_i}$，根据 DP 的定义，我们发现随着左端点的变小，右端点单调不升，所以我们可以维护一个 DP 值的桶，每次更新左端点时将右端点一直往左扫直到扫到存在的地方为止。

总时间复杂度为 $O(m \ln m)$。

题意

给定 $k$，你需要构造一个长为 $n$ 的序列 $A$，满足：

1. $\forall i \in [1, n], A_i \in [-10^{16}, 10^{16}]$。
2. 恰有 $k$ 个 $a$ 的子集 $s$ 满足 $s$ 和为 $0$（含空集）。
3. $n \in [0, 30]$。

题解

构造 + 背包神仙题。

首先我们考虑将构造的 $A$ 序列拆成两部分，$a$ 序列和 $b$ 序列，且 $a$ 序列与 $b$ 序列满足以下要求：

1. 对于所有的 $i$ 都有 $a_i > 0$。

2. 记 $a$ 序列的和为 $sum$，对于所有的 $i$ 都有 $b_i < -\frac{sum}2$。

根据这些要求，不难看出，$A$ 序列和为 $0$ 的子集要么为空集，要么是 $a$ 的子集与 $b$ 的其中一个元素组成的，所以 $b$ 的每个元素对于和为 $0$ 的子集的贡献是独立的。

我们考虑随机构造出 $a$ 序列，然后对于每一个 $x$ 预处理出 $x$ 如果加进 $b$ 序列内会造成多少贡献，这个可以用背包 dp 解决，再对于每一个 $k$ 预处理出最小的满足要求的 $b$ 长度，这个也可以用背包 DP 解决并记录方案，然后对于每一组数据回答即可。

实际上满足 $|a| = 22$ 且值域为 $[1, 5]$ 的序列 $a$ 足以通过本题。

题意

link

有 $n$ 张牌，每张牌两面各写有一个数字。第 $i$ 张牌正面写着 $a_i$，反面写着 $b_i$，且保证 $a$ 序列和 $b$ 序列都是 $1 \sim n$ 的排列。

有多少种选择牌的方案使得对于每一个 $1 \le i \le n$ 的 $i$，$i$ 至少在选择的一张牌上出现（无论正反面）过？

题解

我们考虑 $n$ 个节点 $n$ 条边的一张图 $G$，节点标号由 $1 \sim n$，第 $i$ 条边连接 $a_i$ 和 $b_i$，然后这个问题就转化成了求出 $G$ 的边覆盖方案数。

由于 $a$ 和 $b$ 都是 $1 \sim n$ 的排列，$G$ 肯定是若干个互不影响的环，答案显然是每一个环的方案数的乘积。现在，问题就再次简化，求出大小为 $m$ 的环的边覆盖方案数，令其为 $g(i)$。

我们首先考虑求出另一个问题：有 $m$ 个排成一排的元素，每两个相邻的元素中必须至少选一个的方案数，令其为 $f(i)$。这个问题很简单，直接 $O(m)$ DP 解决即可。

然后我们回到原问题。考虑环上的某一条边，如果选了这条边，环的剩余部分就变成了一条长度为 $m - 1$ 的链，每两条相邻的边中必须至少选一条，方案数为 $f(m - 1)$；如果不选这条边，这条边相邻的两条边会被强制选择，剩余部分是一条长度为 $m - 3$ 的链，方案数为 $f(m - 3)$。最后，我们得到 $g(m) = f(m - 1) + f(m - 3)$。

题意

link

有一个 $n \times m$ 的棋盘，你需要把 $b$ 个黑车和 $w$ 个白车都放在棋盘上，满足：

• 每个格子里最多只能放一个车。
• 没有任意一对不同颜色的车可以互相攻击。

求放车的方案数对 $998244353$ 取模的值。注意，相同颜色的两个车不区分。

题解

首先，我们考虑什么情况下没有任意一对不同颜色的车可以互相攻击。设有黑车的行集合为 $rb$，有黑车的列集合为 $cb$，有白车的行集合为 $rw$，有白车的列集合为 $cw$，显然 $rb \cap rw = \empty$ 且 $cb \cap cw = \empty$。

于是，设 $f(i, j, x)$ 为在 $i \times j$ 的棋盘里放 $x$ 个车，并满足每行每列都至少有一个车的方案数，答案即为：

$\sum_{i = 1}^n\sum_{j = 1}^{n - i}\sum_{k = 1}^m\sum_{l = 1}^{m - k} C_n^i C_{n - i}^j C_m^k C_{m - k}^l f(i, j, b)f(k, l, w)$

考虑枚举 $|rb|, |rw|, |cb|, |cw|$，再乘上选出这些行和列的方案数。白车只能放在 $rw$ 和 $cw$ 里，这些可以放的格子形成了 $|rw|\times|cw|$ 的棋盘，黑车同理。

思考如何求出 $f(i, j, x)$。考虑容斥，”每行每列都至少有一个车“可以变成 $C_{ij}^x$ 减去至少有一行或一列没放车的方案数。

于是我们得到式子：

$f(i, j, x) = C_{ij}^x - \sum_{1 \le k \le i, 1 \le l \le j, (k, l) \not= (i, j)} C_i^k C_j^l f(k, l, x)$

分别求出 $f(i, j, b)$ 和 $f(i, j, w)$ 即可做到 $O(n^2m^2)$ 求答案。

题意

link

给你一棵 $n$ 个节点的树与一个正整数 $m$，第 $i$ 个节点有一个点权 $a_i$（满足 $1 \le a_i \le m$），设一条链包含 $p_1, p_2, p_3, \dots, p_k$ 共 $k$ 个点，则这条链的权值为 $k \times \gcd_{i = 1}^k\{p_i\}$，请求出这棵树上所有链的权值之和对 $998244353$ 取模的值。

题解

这题看起来像点分治，但实际上和点分治没什么关系……

考虑枚举 $\gcd$。

设 $f_i$ 为 $\gcd$ 为 $i$ 倍数的链长度总和，$g_i$ 为 $\gcd$ 为 $i$ 的链长度总和，答案显然为 $\sum_{i = 1}^m i \times g_i$，我们只要计算出 $f$ 就可以在 $O(m \ln m)$ 的时间内根据公式 $g_i = f_i - \sum_{i | j} g_j$ 算出 $g$。

$f_i$ 怎么求呢？将所有点权是 $i$ 的倍数的点以及连接这些节点的边提出来，可以构成一片森林，在这片森林的每一棵树中分别求解所有链长度总和加起来就是 $f_i$。每一棵树的所有链长度总和可以用换根 DP 简单求解。

设 $d(x)$ 为 $x$ 的约数个数，则第 $i$ 个点只会被考虑 $d(a_i)$ 次，求解 $f$ 的时间复杂度为 $O(nd(m))$；总时间复杂度为 $O(nd(m) + m \ln m)$。

题意

link

有 $n$ 个盒子，第 $i$ 个盒子里有 $a_i$ 个小球，然后会执行 $k$ 次操作，每一次操作等概率随机在所有盒子中选出一个，在选择的盒子里放上一个小球，请求出执行完 $k$ 次操作之后每个盒子里小球数量的乘积的期望对 $998244353$ 取模后的值。

题解

因为是等概率随机，所以这个期望很假，求出所有放球方案的乘积总和除以 $n^k$ 即为期望。

首先考虑 $a_i$ 都为 $0$ 的情况的方案数。

设 $s_{i, j}$ 为第 $i$ 秒是否在第 $j$ 个盒子里放了球，如果是则为 $1$，否则为 $0$。对于一种情况，它对答案的贡献显然是 $(s_{1, 1} + s_{1, 2} + \dots + s_{1, k})(s_{2, 1} + s_{2, 2} + \dots + s_{2, k}) \dots (s_{n, 1} + s_{n, 2} + \dots + s_{n, k})$，如果我们把它拆开，可以发现得到的式子的每一项都形如 $s_{1, t_1}s_{2, t_2} \dots s_{n, t_n}$，共有 $k^n$ 项，其中有 $1 \le t_i \le k$。还可以发现每一项都是 $0$ 或 $1$，且一项是 $1$ 当且仅当 $\forall i \in [1, n] s_{i, t_i} = 1$。

根据乘法原理，我们只需要算出两个东西，确定 $t_i$ 使得确定 $s_{i, j}$ 后该项可能为 $1$ 的方案数，与在确定 $t_i$ 的情况下确定 $s_{i, j}$ 使得该项为 $1$ 的方案数，它们的乘积即为答案。

对于前者，我们发现只有 $t_i$ 两两不同时确定 $s_{i, j}$ 后才可能为 $1$（因为对于每个 $i$ 在，所有的 $j$ 中 $s_{i, j}$ 只能恰好有一个为 $1$），方案数为 $\dfrac{k!}{(k - n)!}$；对于后者，考虑每一个 $i$，在存在一个 $j$ 使得 $t_j = i$ 时 $s_{i, j} = 1$，其他 $s_i$ 都为 $0$，只有一种方案；否则 $s_i$ 可以任选一个位置等于 $1$，其它位置都为 $0$，有 $n$ 种方案，方案数为 $n^{k - n}$，答案即为 $\dfrac{k!n^{k - n}}{(k - n)!}$。

现在我们回到原问题，设 $b_i$ 为第 $i$ 个盒子的增量，我们发现要求的是这样一个式子：$\prod_{i = 1}^n (a_i + b_i)$。

把它拆开，发现每一项都是 $x$ 个 $a_i$ 与 $n - x$ 个 $b_i$ 相乘，所以我们只需要预处理出 $f_i$ 和 $g_i$，$f_i$ 代表 $a$ 部分的答案，$g_i$ 代表 $b$ 部分的答案，$\sum_{i = 0}^n f_ig_{n - i}$ 即为总答案。$f$ 可以用 DP 在 $O(n^2)$ 的时间内求出，而类比前面的问题，$g_i = \dfrac{k!n^{k - i}}{(k - i)!}$。

总时间复杂度为 $O(n^2)$。

题意

link

有一个长度为 $n$ 的序列 $a$，还有一个空的序列 $b$ 和一个空的栈 $s$，接下来按下标顺序考虑 $a$ 的每一个数，设当前考虑的数为 $x$，可以选择忽略它或把它移动到 $s$ 的顶部。

此外，在任何时刻，只要 $s$ 不为空，就可以把 $s$ 的栈顶弹出，移到 $b$ 的末尾。

你需要保证 $b$ 序列单调不降，请最大化最终 $b$ 序列的长度。

题解

神仙区间 DP。

首先，对于所有不出现在最终 $b$ 序列里的数，在考虑到它的时候都可以直接忽略掉，所以 $s$ 最后一定可以为空。其实，上述过程就相当于把一个序列中的一些数（未被忽略的数）使用一个栈升序排序。

我们考虑把元素放入栈的过程，如果我们要把这些元素中未被忽略的升序排序，这个栈一直都要满足单调性，即，这个栈的元素从顶至底单调不降。然后可以据此发现一个关键的性质：设这些元素中未被忽略的最大值为 $x$，当 $x$ 第一次要进栈时，栈一定为空。所以，最终的 $b$ 序列可以按顺序分为三段：$x$ 第一次出现前形成的序列 $b1$，$x$ 第一次出现后形成的序列 $b2$，$x$。

设 $x$ 第一次不被忽略的位置为 $p$，则 $b1$ 是由原序列 $[1, p - 1]$ 部分组成的，$b2$ 是由原序列 $[p + 1, n]$ 部分组成的。设 $b$ 序列值域为 $[L, R]$，那么一定存在一个 $m (L \le m \le R)$ 使得 $b1$ 的值域在 $[L, m]$，$b2$ 的值域在 $[m, R]$。于是我们想到区间 DP：$f_{i, j, l, r}$ 表示原序列 $[i, j]$ 部分只考虑值域在 $[l, r]$ 内的数能生成的子序列的最长长度。经过刚才的讨论，转移很容易推出：

$f_{i, j, l, r} = \max(f_{i, j, l, r - 1}, \max_{i \le p \le j, a_p = r} \max_{l \le k < r}\{f_{i, p - 1, l, k} + f_{p + 1, j, k, r} + 1\})$

时间复杂度为 $O(n^5)$。

题意

战士哥手中有 $n$ 张牌，依次编号为 $1\dots n$，第 $i$ 张牌的属性为 $a_i$。

战士哥可以出若干次牌，前提是：对于某个位置 $i\in[2,n-1]$ 满足 $a_i=\dfrac{a_{i-1}+a_{i+1}}2$ 时，他可以消耗第 $i$ 张牌，之后其余的牌自动向前填补空位。请你告诉他，他出牌后的手牌数量最小是多少。

题解

显然，题目给出的条件相当于 $a_{i + 1} - a_i = a_i - a_{i - 1}$，也就是相邻两项差相等。所以我们考虑差分，构造长度为 $n - 1$ 的差分数组 $b$，令 $b_i = a_{i + 1} - a_i$。删除 $i$ 后，$b_{i - 1}$ 和 $b_i$ 会合并，则问题就转化成：一个长度为 $n - 1$ 的数组 $b$，每次可以选择一个 $i(1 \le i < n - 1, b_i = b_{i + 1})$，将 $b_i$ 和 $b_{i + 1}$ 合并，新得到的元素为 $2b_i$，最小化最终序列的长度。

考虑动态规划，令 $f_i$ 为前 $i$ 个元素最少能剩下几个，然后考虑合并后最后一个元素是什么。显然，设它为 $x$，那么 $x$ 一定能表示成 $2^yb_i$ 的形式，且一定满足 $y \in [0, \log v]$。预处理出 $p_{i, j}$ 表示 $p_{i, j} \sim i$ 这一段可以合成为 $2^jb_i$，于是转移方程为 $f_i = \min_{0 \le j \le \log v}\{f_{p_{i, j} - 1} + 1\}$，最终答案为 $f_{n - 1} + 1$，时间复杂度为 $O(n \log v)$。

题意

有一个序列和三个操作，操作分别是区间加、区间赋值和单点查询。

序列长度 $n$、询问次数 $q$、单点查询的次数 $k$ 和两种修改操作的值域 $v$ 是给定的，即其他两种操作共有 $q − k$ 次。初始时，序列中所有的数均为 $0$。

接下来，将这 $q − k$ 次修改操作随机划分为 $k$ 段，并在每段后按顺序插入单点查询的操作，在这些方案中等概率选取一种划分方案。

每次单点查询的位置 $p_1, p_2, \dots, p_k$ 已经确定，并以下面的方式生成另外两种操作：

• 在 $1 \sim V$ 中随机生成一个操作参数，并随机一个操作类型。
• 在 $1 \sim n$ 中随机生成两个数 $x, y$，并以它们中的较小值为左端点，较大值为右端点。
• 不难发现，每次操作都有 $2n^2V$ 种可能，它们之中等概率选取一种。

每次单点查询操作的结果之和的数学期望是多少？

题解

首先，我们可以发现每一个位置的答案是独立的，互不影响。所以我们可以想到递推：设 $f_{i, j}$ 为 $p_i$ 在 $j$ 次修改后的期望值，这个简单做一下即可。

然后，我们再设 $g_{i, j}$ 为所有情况下前 $i$ 个询问点经过 $j$ 次操作后的期望值之和，$s_{i, j}$ 为排列 $i$ 次查询和 $j$ 次修改的方案数，则转移方程为：

$g_{i, j} = \sum_{k = 0}^{j - 1} g_{i - 1, k} + f_{i, j} s_{i, j}$

$s_{i, j} = \sum_{k = 0}^{j - 1} s_{i - 1, k}$

前缀和优化一下即可 $O(k(q - k))$ 完成 dp，答案为 $\dfrac{g_{k, q - k}}{s_{k, q - k}}$。

题意

数轴上有 $n$ 个棋子，第 $i$ 个棋子初始在 $a_i$。

你会不断对棋子进行操作，每次操作是选择一个棋子，假设它的坐标是 $x$，则可以把它移动到 $x-1$ 或 $x-2$，但要求移动后的位置原先没有棋子。

如果一个棋子的坐标变得小于等于 $0$，则称它挂掉了。你需要求出有多少种合法的使棋子挂掉的顺序。

题解

有趣的题。因为棋子只能往前跳，所以前面的棋子只会对后面的棋子造成影响，所以我们从前往后考虑棋子。还能发现，让棋子移动到 $1, 3, 5, 7, \dots$ 的位置是不会堵路且占用空间最小的。维护一个 $c$ 表示目前棋子的数量，以及 $ans$ 表示目前方案数（初始为 $1$），从前往后加入棋子（设当前棋子坐标为 $x$）：

• 如果 $x = 2c$，则目前的 $c + 1$ 个棋子中至少有一个要挂掉，其余棋子补位，令 $ans \gets ans \times (c + 1)$。（不让一个棋子挂掉后面的棋子就走不动了）
• 否则，$c \gets c + 1$。（令新加入的棋子往前移到 $2c + 1$）

最后，留下的 $c$ 个棋子可以任意规定顺序，$ans \gets ans \times c!$。

题意

你有 $A$ 枚正能量骰子，$6$ 个面分别显示的是 $[1, 6]$ 的值。

你有 $B$ 枚负能量骰子，$6$ 个面分别显示的是 $[-6, -1]$ 的值。

你同时投掷这 $A + B$ 枚骰子，如果存在两枚骰子点值的和为 $0$，它们会结对消失。

问结对消失过程结束后，存在点数不超过 $T$ 的正能量骰子的概率。

题解

考虑正难则反，定义 $f(s, i, j)$ 表示还需要掷 $i$ 枚正能量骰子和 $j$ 枚负能量骰子，且投出的绝对值均大于等于 $s$ 的情况下，总共有多少种方案最终是没有小于等于 $s$ 的正能量骰子剩余的，则答案为 $\dfrac{6^{a + b} - f(1, a, b)}{6^{a + b}}$。显然有转移方程：

$f(s, i, j) = \begin{cases} s > t & (6 - s + 1)^{i + j}\\ s \le t & \sum_{x = 0}^i \sum_{y = x}^j \binom ix \binom jy f(s + 1, i - x, j - y) \end{cases}$

前者容易计算，考虑计算后者。柿子可以变形成这样：

$\sum_{x = 0}^i \binom ix \sum_{y = x}^j \binom jy f(s + 1, i - x, j - y)\\$

然后考虑固定 $s$，然后先枚举 $j$。对于每一个 $j$，可以令 $f_j(i, y) = \binom jy f(s + 1, i, j - y)$，这些可以先算出来。然后柿子变成这样：

$\sum_{x = 0}^i \binom ix \sum_{y = x}^j f_j(i - x, y)$

对 $f_j$ 做前缀和即可。时间复杂度为 $O(6n^3)$。

题意

现有 $n$ 个红珠子和 $An+B$ 个蓝珠子，从左往右放珠子，保证任何时候假如有 $x$ 个红珠子，蓝珠子数量不超过 $Ax+B$ 个，问有多少种摆放方法能摆完所有的珠子？

题解

令 $m = An + B$。考虑 $n \times m$ 的网格图，放一个红珠子相当于向右走一步，放一个蓝珠子相当于向下走一步，则方案数等价于从 $(0, 0)$ 走到 $(n, m)$ 且不穿出直线 $Ax + B$ 的方案数。考虑

容斥，枚举第一个穿出的位置（从 $(p, Ap + B)$ 走到 $(p, Ap + B + 1)$），之后，方案数为：

$\begin{aligned} & \binom{n - p + m - Ap - B - 1}{n - p}\\ = & \dfrac{(n - p + m - Ap - B - 1)!}{(n - p)!(m - Ap - B - 1)!}\\ = & \dfrac{(n - p + m - Ap - B - 1)!}{(n - p - 1)!(m - Ap - B)!} \times \dfrac{m - Ap - B}{n - p}\\ = & \binom{n - p + m - Ap - B - 1}{n - p - 1} \times \dfrac{An + B - Ap - B}{n - p}\\ = & \binom{n - p + m - Ap - B - 1}{n - p - 1} \times \dfrac{An - Ap}{n - p}\\ = & A\binom{n - p + m - Ap - B - 1}{n - p - 1}\\ \end{aligned}$

即 $(p, Ap + B + 1)$ 走到 $(n - 1, m + 1)$ 的方案数的 $A$ 倍。设从 $(0, 0)$ 走到 $(p, Ap + B)$ 且不穿出线的方案数为 $f_p$，那么答案为：

$\begin{aligned} & \binom {n + m}n - \sum_{p = 1}^{n - 1} f_p\binom{n - p + m - Ap - B - 1}{n - p}\\ = & \binom {n + m}n - A\sum_{p = 1}^{n - 1} f_p\binom{n - p + m - Ap - B - 1}{n - p - 1}\\ = & \binom {n + m}n - A\binom{n + m}{n - 1}\\ \end{aligned}$

在最后一步转化中，我们发现 $p$ 枚举的是第一个穿出线的位置，加起来就是总方案数，所以可以直接转为 $\binom{n + m}{n - 1}$。

题意

link

$n$ 个人正在考试。目前第 $i$ 个人有一个得分 $a_i$，想要及格需要拿到 $l_i$ 分。而为了不被老师怀疑，他的分数不能超过 $r_i$。

你可以组织若干场作弊。这些作弊是同时进行的，所以不能有人同时参加两场或以上的作弊。每场作弊在连续的一段考生中进行，他们的分数都变为他们中分数最高的人的分数。

求最多能使多少人及格且不被怀疑。

题解

考虑暴力 DP，设 $f_i$ 为前 $i$ 个数的答案，$mx(i, j)$ 为 $\max_{k = i}^j a_k$，$s(i, j)$ 为 $[i, j]$ 都赋值为 $mx(i, j)$ 能满足要求的人数，那么 $f_i = \max_{j = 1}^i\{f_{j - 1} + s(j, i)\}$。如果我们想要用数据结构优化 DP，动态维护 $s$ 是必不可少的。

但是直接计算 $s$ 很麻烦，我们考虑一个数 $a_i$ 什么时候对 $s(x, y)$ 有贡献。考虑求出最大的满足 $mx(j, i) \ge l_i, j \le i$ 的 $j$ 记为 $Ll_i$，最小的满足 $mx(j, i) \le r_i, j \le i$ 的 $j$ 记为 $Lr_i$，最小的满足 $mx(j, i) \ge l_i, j \ge i$ 的 $j$ 记为 $Rl_i$，最大的满足 $mx(j, i) \le r_i, j \ge i$ 的 $j$ 记为 $Rr_i$，那么：

• $i \le y < Rl_i, Ll_i \le x \le Lr_i$ 时 $a_i$ 对 $s(x, y)$ 造成贡献。
• $Rl_i \le y \le Rr_i, Ll_i \le x \le i$ 时 $a_i$ 对 $s(x, y)$ 造成贡献。

然后考虑线段树优化。我们开一棵线段树，假设当前考虑 $f_i$ 的转移，那么线段树的第 $j$ 个位置维护的是 $f_{j - 1} + s(j, i)$。具体过程是这样的：

1. 令区间 $[Ll_i, Lr_i]$ 加一，再对于所有 $Rl_j = i$ 的 $j$，令区间 $[Ll_j, Lr_j]$ 减一。这一部分对应了上面第一个贡献点的更新。
2. 对于所有 $Rl_j = i$ 的 $j$，令区间 $[Ll_j, i]$ 加一，对于所有的 $Rr_j + 1 = i$ 的 $j$，令区间 $[Ll_j, i]$ 减一。这一部分对应了上面第二个贡献点的更新。
3. 令 $f_i$ 为线段树上前 $i$ 个位置的最小值。
4. 如果 $i < n$，令第 $i + 1$ 个位置加上 $f_i$。

时间复杂度为 $O(n \log n)$。

题目

题解

插入 dp trick。

实际上，原问题相当于让你统计 $p_1 = s, p_n = t, $ 长度为 $n$ 且呈波浪形的排列。

然后考虑按照值域从小到大考虑，同时维护很多的段，每次来一个数可以合并两段或新开一段。

所以可以考虑 dp：设 $f_{i, j}$ 为考虑了前 $i$ 个数，目前有 $j$ 段的方案数，有转移方程：

$f_{i, j} = (j - [i > s] - [i > t])f_{i - 1, j - 1} + j \times f_{i - 1, j + 1}$

$f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j} \ (i = s \| i = t)$

最终答案是 $f_{n, 1}$，时间复杂度为 $O(n^2)$。

题目

题解

首先把值域离散化。

然后我们考虑距离最远的那个外星人 $p$，我们必须要用一次直径为 $d_p$ 的攻击来处理它。然后这次攻击可以在 $x \in [a_p, b_p]$ 时刻发出，并处理掉满足 $a \le x \le b$ 的外星人，此时原问题划分为两个独立的子问题，消灭时间处于 $[1, x - 1]$ 内的外星人，和消灭时间处于 $[x + 1, m]$ 内的外星人。

所以可以考虑一个区间 dp：设 $f_{l, r}$ 为消灭时间处于 $[l, r]$ 内的外星人的最小代价，答案则为 $f_{1, m}$。

转移类似最开始考虑的来转移即可，时间复杂度为 $O(n^3)$。

题目

题解

首先考虑第一问。考虑一个显然的贪心：从前往后考虑，如果当前元素前有比它大的，则将当前元素一直前移直到前面没有比他大的元素，否则不移动。然后实际上这就是 $n \ -$ 前缀最大值个数。

所以我们考虑一个 dp：设 $f_{i, j}$ 为长度为 $i$，需要操作 $j$ 次的排列数。然后转移考虑插入最小值，如果把最小值插入在开头则不用多操作，$f_{i, j} \to f_{i + 1, j}$；否则需要多操作，$f_{i, j} \to i \times f_{i + 1, j + 1}$，答案为 $f_{n, k}$。

然后考虑第二问。既然变成了环排列，那么我们考虑断环成链，那么一个排列的最少次数就是每个位置断环成链后的操作次数的最小值，进而变成求前缀最大值个数的最大值。我们把每个点向它后面第一个比它大的点连一条边，会构成一棵以 $n$ 为根的树，答案则为树高。

然后我们就可以设 $g_{i, j}$ 为大小为 $i$，树高为 $j$，节点从叶到根递增的树的方案数，答案为 $g_{n, n - k}$。然后有转移方程 $g_{i + j, \max(k, l + 1)} = \binom{i + j - 2}{j - 1}g_{i, k}g_{j, l}$，前缀和优化可以做到 $O(n^3)$。

题目

题解

首先我们考虑把这两个序列合并为一个序列 $c$，且所有元素从小到大排序，从序列 $a$ 来的染成红色，从序列 $b$ 来的染成蓝色，则问题变为给序列 $c$ 匹配 $n$ 对不相交异色对，匹配的权值是每一对前面的元素的值的积，求所有匹配方式的权值和。

接下来就可以设状态 $f_{i, j}$ 为 $c$ 序列前 $i$ 个元素中还有 $j$ 个红色元素未匹配的权值和，答案即为 $f_{2n, 0}$，转移看当前元素的颜色分情况讨论，考虑该元素作为前面的元素还是后面的，时间复杂度为 $O(n^2)$。