• 搬题人：
  • A, C：sys
  • B：cdw
• 组题人：FSYo
• 题解：sys，cdw

乘积

题目来源：ABC239 Task Ex (Dice Product 2)

Atcoder 链接：https://atcoder.jp/contests/abc239/tasks/abc239_h

设 $f_i$ 表示当前 $M=i$ 的期望时间，则有 $\displaystyle f_i=1+\frac 1n\sum_{j=1}^n f_{ij}$。

此时我们发现，$\left\lfloor\dfrac mi\right\rfloor$ 相同的 $i$，$f$ 值一样。

所以我们可以设 $g_i$ 表示 $M=1,m=i$ 的值。答案即为 $g_m$。

则有 $\displaystyle g_i=1+\frac 1n\sum_{j=1}^n g_{\lfloor\frac ij\rfloor}$，记忆化搜索即可。

复杂度与杜教筛相同，为 $\displaystyle \int^\sqrt m_2\left(\sqrt x+\sqrt\frac mx\right)\mathrm dx=\mathcal O(m^\frac 34)$。

守卫 2

题目来源：Romanian Master in Informatics 2021, Day 2, Task "Paths".

QOJ 链接：https://qoj.ac/problem/2812

引理 1. 守卫所选目的地均为叶子。

引理 2. $k$ 次贪心选择使得答案增加尽可能多的叶子即可。

证明. 设第 $i$ 次选择的叶子是 $\text{leaf}_i$，答案对应增加了 $a_{\text{leaf}_i}$ 到 $\text{leaf}_i$ 的链；若最优解包含 $\text{leaf}_1,\cdots,\text{leaf}_{i-1}$ 但不包含 $\text{leaf}_i$，

• 若最优解不包含 $a_{\text{leaf}_i}$ 到 $\text{leaf}_i$ 的链，由定义知任意选择最优解所选叶子 $y$ 换为 $\text{leaf}_i$ 不劣；
• 否则找到最优解所选叶子 $y$ 使得 $y$ 与 $\text{leaf}_i$ 的 LCA 深度最大，由定义知将 $y$ 换为 $\text{leaf}_i$ 不劣。证毕。

以 $1$ 为根，设 $\text{down}_v$ 表示 $v$ 子树内距离 $v$ 最远的叶子，$\text{up}_v$ 表示 $v$ 子树外距离 $v$ 最远的叶子。

引理 3. 对于 $r=1$ 的情况，设选择叶子 $x$ 时答案对应增加 $a_x$ 到 $x$ 的链，则 $a_x$ 即为最深的祖先 $v$ 使得 $\text{down}_v\ne x$（若不存在则认为 $v=r$）

引理 4. 将根从 $r$ 移向儿子 $q$ 时，所有 $a_x$ 中仅有 $\text{up}_q$ 和 $\text{down}_q$ 的值会从 $r$ 变为 $q$，其他均不变。

对 $r$ 进行 DFS，维护每个叶子 $x$ 对应的答案增量，支持多重集的单点修改和查询前 $k$ 大值之和即可，时间复杂度 $\mathcal O(n\log n)$。

下降

题目来源：JOISC 2020 Day2 T3 (Ruins 3) （第 19 回日本情報オリンピック　春季トレーニング合宿）

• 情報オリンピック日本委員会作 『第 19 回日本情報オリンピック　春季トレーニング合宿競技課題』 はクリエイティブ・コモンズ 表示-継承 4.0 国際ライセンスで提供されています.
• https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html
• https://loj.ac/p/3276
• https://qoj.ac/problem/3557

考虑 $h \to p$ 的过程。

初始时序列 $B$ 全为 $0$。从 $2n$ 到 $1$ 考虑将 $h_i$ 加入序列 $B$，枚举 $j$ 从 $h_i$ 到 $1$，若 $B_j$ 为 $0$，则在这里填入 $i$。如果没有这样的位置，则其不在 $p$ 中现身。否则令 $p_{B_i}=i$。

而这样，每个位置是否存活取决于 $\textrm{mex}(B)$ 与 $h_i$ 的大小关系。

设 $f_{i, j}$ 表示 $2n$ 到 $i$，$\textrm{mex}=j+1$ 的方案数。答案为 $f_{1, n}$。

为了转移方便，我们可以把高度相同的两个柱子看成不同的元素，最后除以 $2^n$ 即可。

若 $i$ 没有在 $p$ 中出现过，则 $j\geq h_i$，$\textrm{mex}$ 不会改变。$f_{i, j}\leftarrow cf_{i+1, j}$，其中 $c$ 为可以放的数字个数，为 $j-$ 之前放过的无效数字个数。这是由于 $\textrm{mex}$ 是不降的。

若 $i$ 出现过，且没有改变 $\textrm{mex}$，我们将它搁置，直到 $\textrm{mex}$ 改变时统计。因为我们并没有记录除了 $\textrm{mex}$ 之外的信息。$f_{i, j} \leftarrow f_{i+1, j}$。

若 $\textrm{mex}$ 改变了，考虑新的 $\textrm{mex}=j+k$，则考虑先选出 $k-1$ 个在序列中出现过的位置，和 $i$ 在 $B$ 中构成了 $(j, j+k]$。之后再考虑他们的 $h$ 值。要满足 $\leq j+s$ 的数不得超过 $s$ 个。否则就会有一个数走向 $0$，不在 $p$ 中现身。

设这样的方案数为 $g_k$ ，则 $g_k$ 可以非常简单地预处理。

最后，$h_i$ 的取值为 $[j, j+k]$，故乘 $k+1$。

故 $\displaystyle f_{i, j+k}\leftarrow (k+1)\binom {c-j-1}{k-1}g_{k}f_{i+1, j}$。

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