石子合并

idea, data, solution from myee

萌萌出题人给大家带来了一道萌萌签到题！

$n\le4$，$m\le8$

直接 $O(n^m)$ 暴力枚举所有石子放到各个石堆的情况，然后暴力 check 就好啦！

注意处理相同元素时不要计重。

$n=2$，$m\le20$

做法同上，但是 check 部分的常数要写的好一点。

$n\le100$，$m\le300$，$o=1$

对于 $o=1$ 的情况，我们容易发现所有初始石堆内的石子编号都是不降的！

我们不妨考虑 dp，从小到大依次加入石子。

每次加入一段相同的石子时，我们可以选择给已有的石堆往末尾分别加入若干，或者加入某些还没有出现过的石堆。

dp 时需要记录当前已经考虑到哪个石子，以及已经有多少个石堆已经非空了。

复杂度容易做到 $O(n^2m)$。

$n\le100$，$m\le300$，$o=0$

现在有下降的石子编号了，我们咋办？

我们考虑一下归并的过程：如果第一个石堆里的某个石子 x 后面有一堆比当前石子小的石子，那么当合并时加入 x 后，x 后面一堆编号比 x 小的石子会跟着一起加入，而且仍然保持跟在 x 后面。

因此，我们可以把这些 x 后面比 x 小的石子“归附”到 x 上，容易发现合并过程是不变的！

对于最后合成的序列，当一个石子比前面的任意某个石子小的时候，其一定归附在前面的某个石子上，因此删除其不影响答案！

这样我们就转化成了石子编号不降的情况，直接采用 $o=1$ 时的算法即可。

$n\le1000$，$m\le3000$

同样我们只考虑 $o=1$ 的情况。

之前我们的 dp 没有前途，考虑有没有什么比较优秀的做法。

我们观察到，之前的做法复杂度比较高是因为题目里这个「非空」的限制很棘手。

如果没有这个非空的限制，那我们怎么计数呢？

我们假设有 $c_j$ 个石子编号为 $j$，当前有 $n$ 个石堆，而石堆可以为空，那么答案 $f_n$ 为

$$ f_n=\prod_{j=1}^m\binom{c_j+n-1}{c_j} $$

理由是显然的：只用对每种编号的石子考虑插板法即可。

然而答案要求每个石堆均非空，我们设这样的答案为 $g_n$。

我们尝试考察 $f_n$ 和 $g_n$ 的关系，容易发现

$$ f_n=\sum_k\binom nkg_k $$

理由是，我们可以枚举当前哪些石堆是非空的，而剩下的石堆都是空的。

那么很自然的考虑二项式反演（不会？可以去 vfk 的博客里学）：

$$ g_n=\sum_k(-1)^{n-k}\binom nkf_k $$

因此我们只用求出 $f_0\sim f_n$，就可以解出 $g_n$ 辣！（你也可以直接使用组合意义容斥得到一样的结果）

直接按照第一个公式暴力处理就是 $O(nm)$ 的了。

$n\le2\times10^5$，$m\le5\times10^5$

我们发现问题的关键在于要快速算出 $f_0\sim f_n$。这咋办？

我们考虑观察一下特殊性质。

特殊性质：$a_i\le20$

这种情况下我们只用枚举 $j\le20$ 的情况，更大的情况因为 $c=0$ 而不用考虑。

特殊性质：$c_j\le5$

我们考虑到对于同样的 $c$，$\binom{c+n-1}{c}$ 是相同的，我们不妨考虑统计有多少个数 $j$ 对应的 $c_j=k$，即记

$$ t_k=\sum_{j=1}^m[c_j=k] $$

那么我们就有

$$ f_n=\prod_k\binom{k+n-1}{k}^{t_k} $$

直接处理即可。

一般情况

实际上有多少 $k$ 满足 $t_k>0$ 呢？

我们注意到

$$ \sum_{k>0}kt_k=\sum_jc_j=m $$

因此实际上满足 $t_k>0$ 的 $k$ 不会多于 $O(\sqrt m)$ 个！

直接暴力计算所有 $f$ 即为 $O(n\sqrt m)$ 的。

总复杂度 $O(m+n\sqrt m)$，可以通过本题。

快速幂的 $\log$ 去哪了

那肯定有同学要问了：快速幂部分的 $\log$ 怎么没有进入复杂度呢？

其实是因为，我们计算 $f$ 的复杂度实际上为

$$ O(n\sum_{t_k\ge1}\log t_k) $$

而

$$ \sum_{t_k\ge1}(1+\lfloor\log_2t_k\rfloor)=\sum_{p\ge0}\sum_k[t_k\ge2^p]=\sum_{p\ge0}\sum_k[\lfloor\frac{t_k}{2^p}\rfloor>0] $$

而我们显然有

$$ \sum_kk\lfloor\frac{t_k}{2^p}\rfloor\le\frac m{2^p} $$

因此

$$ \sum_{p\ge0}\sum_k[t_k\ge2^p]=O(\sum_{p\ge0}\sqrt{\frac{m}{2^p}})=O(\sqrt m) $$

从而计算 $f$ 的复杂度仍然为 $O(n\sqrt m)$。

一个更优的做法

我们考虑到

$$ f_{n+1}/f_{n}=\frac{1}{n^m}\prod_{j=1}^m(n+c_j) $$

因此问题的关键在于对 $k=1,2,\dots,n$，计算出

$$ \prod_{j=1}^m(k+c_j) $$

使用多项式多点求值算法或者多项式连续点值平移可以直接做到 $O(m\log^2m)$。

能不能再给力点啊？

我们注意到 $0 < k+c_j\le n+m<\textbf{Mod}$，其中 $\textbf{Mod}=998244353$，因此我们设在以原根为 $g=3$ 意义下 $j$ 的离散对数为 $s_j$，满足 $g^{s_j}\equiv j\pmod{\textbf{Mod}}$，那么我们就只用对 $k=1,2,\dots,n$ 求出

$$ h_k\equiv\sum_{j=1}^ms_{k+c_j}\pmod{\textbf{Mod}-1} $$

很显然我们有

$$ h_k\equiv\sum_{j=1}^ms_{k+j}t_j\pmod{\textbf{Mod}-1} $$

这就是一个差卷积的形式，使用 MTT 即可在 $O(m\log m)$ 的时间内解决。

问题来到计算 $s_{1\sim n+m}$ 上，我们使用线性筛的方法，只用计算质数处的 $s_p$ 值，然后直接套用 Pohlig–Hellman algorithm 即可。由于 $998244353$ 的优秀性质，计算单个离散对数的复杂度可以近似认为是 $O(\log\textbf{Mod})$ 的。

总复杂度不会超过 $O(m\log\textbf{Mod})$。

街头庆典

idea, data from 1kri, solution from 1kri, zhoukangyang

分析

考虑找到一组割掉边数最少的最优解，去分析这种最优解的结构。在这组最优解中，每条割掉的边都是不能省去的。

那么对于每条被割掉的边，它的两个端点一定是所在连通块中某条直径的端点。否则如果不割掉这条边，直径长度和也不会变大。

进一步分析，对于一个连通块，找到它的中心（直径的中点，有可能在某条边中间），那么它外围的所有端点（除了原树中的叶子节点）与这个中心的距离一定相等。换言之，每个连通块都恰包含了到某个中心距离不超过一个定值的所有节点。

我们考虑以某个原树的直径端点为根，这时我们发现，对于最终的每个连通块，都有一条直径以其深度最浅的点为端点。

算法一

以某个直径端点为根。

考虑 $\text{dp}$，设 $f_u$ 表示 $u$ 到父亲的边被割掉，$u$ 子树内的最小代价。然后设 $s_{u,d}$ 表示 $u$ 子树内，割掉所有与 $u$ 距离为 $d$ 的边，代价之和。

我们记 $g_{u,i}$，它的含义是 $u$ 号点所在连通块的中心在 $u$ 子树内，且到其所在连通块内深度最浅点的距离为 $i$，最小贡献。显然 $g_{u,0}$ 表示的就是 $f$。

对于 $g$ 数组，分三种情况转移：中心是 $u$，中心在 $u$ 到某个儿子的边上，中心在 $u$ 的某个儿子的子树内。

对于三种情况，都容易写出 $g$ 的转移式。

以第三种情况为例，$g_{u,i} = \min\limits_v g_{v,i+1}+s_{u,i}-s_{v,i-1}$。其含义是，因为连通块是满的，所以 $u$ 子树中除 $v$ 子树以外要割掉恰好某个深度的所有边。

直接转移，时间复杂度 $O(n^2)$，可以得到 $40$ 分。

算法二

我们对树进行长链剖分，对于每条长链同时处理答案。

假设现在处理的是包括根的长链，对于其余长链都已计算得到答案。

考虑一种特殊的情况，这条长链上的点所在的所有连通块的中心都在长链上。不难发现，这个限制等价于每个连通块都有直径完全在长链上。

我们设 $val_{l,r}$ 表示长链上第 $l$ 到第 $r$ 个节点构成了一个连通块直径。那么 $val_{l,r}$ 大约形如 $\sum\limits_{i=l}^r s'_{i,\min(i-l,r-i)}$。其中 $s'_{i,d}$ 为长链上第 $i$ 个节点，割掉长链外所有距离其为 $d$ 的边的贡献。

改令 $f_l$ 表示长链上第 $l$ 个节点的原 $f$ 值。那么 $f_{l}$ 形如 $\min\limits_{r=l}^t f_r+val_{l,r}$ 再加上一些只与 $l$ 和 $r$ 有关的简单贡献（其中 $t$ 为长链上的节点个数）。

我们从大往小处理每个 $l$，类似扫描线，动态更新每个 $r$ 的 $val_{l,r}+f_r$。考虑从 $l$ 处理到 $l-1$，在所有 $val_{l,r}$ 计算的过程中有哪些 $i$ 的贡献会发生变化。

当 $r-i \leq i-l$ 或 $i-l > \text{mx}_i$ 时，$i$ 就不会再发生变化了（$\text{mx}_i$ 表示 $i$ 下挂的短子树的最大深度）。

又由于每条长链下挂的短子树最大深度和是 $O(n)$ 的，所以发现每个 $i$ 的贡献发生变化的时刻一共只有 $O(n)$ 个。

对于每次 $i$ 的贡献发生变化，它恰会同时影响一段后缀的 $r$ 的 $val$ 值。这是不难理解的，因为它只会影响 $i-l < r-i$ 的 $r$，且影响只会与 $l$ 有关而与 $r$ 无关。

长剖维护 $s'$ 的值，用线段树优化 $\text{dp}$，能做到 $O(n \log n)$ 的复杂度。

然而这个算法是建立在只处理包括根的长链且这条长链上的点所在的所有连通块的中心都在长链上的假设上的，无法获得什么分数。

算法三

还是考虑只处理包括根的长链，而允许长链上的点所在的连通块的中心在短子树内（或下挂短子树的边中）。

再重新考虑算法一中的 $g$ 数组。发现 $g$ 的第二维范围不能超过 $u$ 子树中的最大深度，那么就自然想到长链剖分。

而这里不能直接长链剖分，是因为当中心在长链上时，第一、二种转移需要数组对位取 $\text{min}$，而且位数是整个子树而非短子树的最大深度，长链剖分无法保证时间复杂度。

而对于只考虑连通块中心在每条长链下挂的短子树内（或连接其的边上）时，就可以规避掉影响时间复杂度的部分了。

发现长链剖分可以解决所有中心不在长链上的转移，而算法二中的扫描线可以解决所有中心在长链上的转移，这两部分拼在一起就得到了所有可能的转移！

那么我们直接同时施加两种方法，就可以得到所有正确的 $f$ 值了！

这个算法只考虑了处理包括根的长链的情况，而没有考虑对于其它长链怎么计算 $g$ 的值，因而也无法获得什么分数。

算法四

现在唯一的问题是要求出 $g$ 值，并且我们发现，在计算过程中，只用到了链顶的 $g$ 值。

我们假设长链上的节点是从 $0$ 编号的，并在长链上新增 $t$ 个虚点，由深至浅标号为 $-1,-2,...,-t$。

那么我们发现，$g_{0,i}$ （这里 $g$ 的第一维同样用点在长链上的位置表示）的含义与 $f_{-i}$ 的含义几乎相同！

唯一的区别是，$-i$ 所在连通块的直径中心不能在 $0$ 以上。这等价于，要么中心在短子树上，要么直径下端点（$r$）不小于 $i$。前者和之前是完全一样的，后者只要改一改原来线段树查询的区间，而对于其它过程都是一样的！

这样，我们通过类似求 $f$ 的过程就可以求出所有的 $g_{0,i}$ 了。

这时，我们的算法不建立在任何假设之上，可以以 $O(n \log n)$ 的时间复杂度通过所有数据。

更进一步，发现线段树的部分是可以由并查集替代的，就能做到 $O(n\alpha(n))$ 甚至是线性！

由于时间限制十分宽裕，只要复杂度正确的做法都能通过。如果不会写复杂的长剖，甚至可以全部用线段树和线段树合并替代。

铁轨回收

idea, data, solution from zhoukangyang

算法 1

我会观察数据范围！

发现有 $B_n = 0$ 的分，输出 $1$ 即可。期望得分 $10$ 分。

算法 2

我会暴力！

模拟题意，时间复杂度 $\Theta((n-1)!)$，拼上算法 1 期望得分 $20$ 分。

算法 3

从前到后 DP，记录一个长度为 $B_n+1$ 的数组 $c$。$c_i$ 代表了后面的点中被加了 $i$ 的有 $c_i$ 个（如果被加了超过 $B_n$ 那就认为加了 $B_n$）。

期望得分 $50$ 分。

算法 4

留给实现得不好的正解。

而 Melania 同学用厉害 DP 过掉了 $B_n \le 10$，在这里向他献上真挚的膜拜！

期望得分 $70 \sim 80$ 分。

算法 5

在后面的描述中，我们记题面里的 $A_i$ 为 $A'_i$，执行完 $1 \sim i - 1$ 的操作后第 $i$ 个仓库有的铁轨长度为 $A_i$。

假设第 $i$ 个仓库选择了第 $j$ 个仓库放铁轨放置，我们就连一条 $i \to j$ 的边。显然这些边形成了一颗以 $n$ 为根的有根树。

我们考虑统计执行完 $1 \sim i - 1$ 的操作后，$A_i=j$ 的方案数：

• 对于 $j < B_i$，我们只要统计 $[A'_i + \sum_{t \in son_j} A_t = j]$ 的方案数即可。
• 对于 $j = B_i$，我们用总方案数减去 $j < B_i$ 的方案数。

这样，我们可以枚举答案 $i$，然后从后往前做 DP：

记 $dp_{pos,S,k}$ 表示在第 $pos$ 个位置之后的点中，需要被连的 $A$ 之和 的集合为 $S$ ，且有 $k$ 个点可以任意接受边（对于一个选择了统计 “总方案数” 的点，他的子树是什么值不重要，因此他前面的任意点都可以向他连边）。

转移可以考虑以下几种情况：

• $fa_{pos}$ 为那 $k$ 个点中的一个，此时 $k \leftarrow k+1$。
• 统计 $A_{pos} = B_{pos}$，并选择”统计总方案数“：此时 $k \leftarrow k+1$，并选择 $S$ 中的一个元素减去 $B_{pos}$。
• 统计 $A_{pos} = B_{pos}$，并选择”减去 $j < B_{pos}$ 的方案“，即做 $-1$ 的贡献。此时选择 $S$ 中的一个元素减去 $B_{pos}$，然后在 $S$ 中加入一个 $t < B_{pos}$ 的 $t-A'_{pos}$。
• 统计 $A_{pos} < B_{pos}$ 的贡献。此时选择 $S$ 中的一个元素减去 $A_{pos}$，然后在 $S$ 中加入 $A_{pos}-A'_{pos}$ 。

注意到 $S$ 中的元素和是单调不升的，因此状态数只有分拆数级别！

我们再把 DP 倒过来做（或者说，转置原理），就可以用一遍 DP 求出答案了。

预处理一下状态之间的转移，时间复杂度上界为 $O(n^2 \pi (B_n) B_n^{1.5})$，期望得分 $100$ 分，其中 $\pi(B_n)$ 是 $B_n$ 的分拆数。