Goodbye Gengzi 题解

由于撞上冬令营以及一些管理员们的个人原因，这次的准备时间非常仓促，即使管理员考前熬了几次夜也难以称得上进行了充分的准备，C 题和 E 题还发生了暴力通过的事故，先在此表示道歉！

新年的饮食方案

Idea, data, std from MatKave, solution from rushcheyo

良心送温暖大水题~

算法一

题目要最小化最大值，不妨二分答案，下面判断答案 $x$ 是否可行。

显然第 $i$ 个米其林精品要在 $[a_{i}, b_{i} + x]$ 中选一天吃。这是一个经典问题，按左端点排序贪心即可。

具体的，我们考虑左端点最小的区间 $y$ ，假如只有一个，那么它一定在第 $a_{y}$ 天被吃，否则移到第 $a_{y}$ 天不会产生冲突；同理地，若有多个左端点最小的区间，我们显然会在第 $a_{y}$ 天吃右端点前 $m$ 小的。我们扫过天数，用堆维护现在可以吃且没被吃的区间即可。

复杂度 $O (n \log^{2} n)$ ，期望得分 $65$ 分，实际得分 $100$ 分。

算法二

咦上面的算法中二分答案好像没啥用？直接去掉就好了！复杂度 $O (n \log n)$ ，期望得分 $100$ 分。

具体地，上面每次二分的过程中，左端点排序的结果并没有变，左端点相同时由于右端点都加了 $x$ ，相对顺序也没有变，所以直接拿堆扫过去并更新答案就好了。

新年的密码锁

Idea, solution from rushcheyo, data, std from skip2004

算法一

首先要做一步 easy 的转化：

存在两条链都不连通当且仅当存在一条边不被任意一条链经过，而且两边都有链。

充分性是显然的，必要性考虑反证：任意两条路径都是连通的。这也是显然的，我们在两条路径上各取一个点，把这两个点树上路径每条边都随便取一条链，就整出了一条路径。

那么给定 $m$ 条链时，我们只需要枚举一条边，使得边两边都存在链，然后用经过这条边的链数更新答案即可。这样我们得到 $O (n q)$ 的做法，期望得分 $48$ 分。

算法二

下面就要用数据结构维护了。

先考虑链的情况，我们可以直接对每条边维护：子树内的链数 $X$ 、子树外的链数 $Y$ 和经过这条边的链权和 $Z$ 。然后线段树上维护 $X$ 的最小值、 $Y$ 的最小值、 $Z$ 的最小值、 $X$ 不取到最小值时 $Z$ 的最小值， $Y$ 不取到最小值时 $Z$ 的最小值、 $X$ 和 $Y$ 均不取到最小值时 $Z$ 的最小值，之后判一下前两项是不是 $0$ 就能轻松算答案。这样结合算法一能拿到 $71$ 分。

上树的话，我们发现每次是对 $X$ 到根加，对 $Y$ 全局加再减掉两条链的并，对 $Z$ 链加。拿树剖等维护可以做到 $O (n \log^{2} n)$ 或 $O (n \log n)$ 。期望得分 $100$ 。

算法三

上面这个做法好难写啊！注意为了选手~~和出题人~~身体健康本题只有加入操作，每条边的状态（子树内有链，子树外有链）只会变化 $O (1)$ 次，可以用并查集 / 链表等找到每次边状态的变化而不是暴力维护 $X / Y$ 。期望得分 $100$ 。

算法四

上面这个做法还是好难写啊！注意问题是离线的，考虑倒着做，每次删掉一条链。我们称一条边的贡献是覆盖它的链的权值和。考虑这条链经过的贡献最小的边，如果这条边合法而且等于之前的答案，那么本次选这条边就是答案；如果这条边不合法，以后更不可能合法，将其贡献改为 $+ \infty$ 即可；如果合法但无法更新答案，那我们一条条检查现在贡献最小的边，合法就停止并输出答案，不合法就将其贡献改为 $+ \infty$ 。于是我们把并查集 / 链表都去掉了。期望得分 $100$ 。

新年的聚会

本题大家纷纷通过了，但是有几位选手可以证明甚至是相信自己算法的时间复杂度呢？

Idea, data, std from skip2004, solution from mayaohua

mayaohua 和 skip2004 讨论后想出了标算。

算法一

题意其实就是给一个 $n$ 个点的无向图，每次可以询问一个点集是否是独立集，要求还原出整张图。

一个暴力的想法是依次枚举所有点对 $(u, v) (u < v)$ ，分别询问这些点对是否是独立集（即它们间是否有边）。

询问次数和点集大小和都是 $O (n^{2})$ 级别的，期望得分 $25$ 分。

算法二

考虑一个剥独立集的做法：每次从图中删去一个极大的独立集（剩余点均和这个独立集中点有边），然后递归还原剩下的子图，再还原独立集中的点和不在独立集中的点间所有边。寻找独立集的时候只需要依次加入每个点，询问现在的极大独立集加上这个点后是否仍为独立集。还原边时，可以枚举不在独立集中的每个点，尝试二分出它和该独立集间的所有边。

不算还原边的部分询问次数为 $O (m)$ ，而每次寻找一条边需要 $O (\log n)$ 轮，于是总询问次数是 $O (m \log n)$ 级别。

不算还原边的部分点集大小和为 $O (n^{2})$ ，而寻找一条边时直接二分的话，容易证明点集大小和是 $O (n m)$ 的，如果做一个小优化，每次寻找某个点和一个独立集间的所有边时进行整体分治，可以证明点集大小和是 $O (n^{2} \log (\frac{m}{n}))$ 的。

期望得分 $60$ 分，精细实现的话实际得分 $100$ 分。

算法三

初始时随机打乱所有点。

考虑一个分治算法，每次尝试还原出点集 $S$ 内的所有边。首先将 $S$ 均匀划分为 $L$ 和 $R$ ，递归找出点集 $L$ 和点集 $R$ 内的所有边，然后尝试找出 $L$ 和 $R$ 间的边。

首先将 $L$ 和 $R$ 划分为尽量少的独立集。这可以应用一个贪心策略，每次寻找一个度数最小的点删去，得到一个点序列，接着从后往前给每个点选择任意划分到一个标号最小的独立集，使得不产生冲突。容易证明若 $L$ 内部边数与 $R$ 内部边数总和为 $m s$ ，可以划分出 $O (\sqrt{m s})$ 个独立集。接着将大小 $> 2 \sqrt{m s}$ 的独立集拆分，可以分别将 $L$ 和 $R$ 划分为 $O (\sqrt{m s})$ 个大小为 $O (\frac{| S |}{\sqrt{m s}})$ 的独立集。

随后我们枚举 $L$ 和 $R$ 间的每个独立集对，询问它们的并集是否是独立集。若它们的并集不是独立集，我们尝试找出它们间的所有边，这可以采取一个分治策略：每次同时将两侧均匀分成两半，分别询问 $4$ 组独立集对间是否有边，若某个独立集对间有边则递归下去寻找。

考虑分析这个算法。

首先分析询问次数。

第一部分枚举每个独立集对间寻找它们的并集是否是独立集，这至多询问 $O ({\sqrt{m s}}^{2}) = O (m s)$ 次，而由于是均匀分治，分治树深度 $O (\log n)$ ，容易看出这部分总询问次数是 $O (m \log n)$ 的。

第二部分分治寻找边，容易看出若找到了 $k$ 条边，询问次数是 $O (k \log n)$ 的，因此这部分总询问次数也是 $O (m \log n)$ 的。

那么整个算法的询问次数就是 $O (m \log n)$ 的。

接着分析点集大小和。

第一部分枚举每个独立集对间寻找它们的并集是否是独立集。由于两侧都只有 $O (\sqrt{m s})$ 个独立集，因此点集大小和是 $O (| S | \sqrt{m s})$ 的。

引理 1： $n$ 个点 $m$ 条边的无向图中，随机 $k$ 个点导出子图边数的根号期望是 $O (\frac{\sqrt{m} k}{n})$ 的。

证明：考虑所有 $k$ 个点的导出子图集合 $G_{k}$ ，其中 $| G_{k} | = (\binom{n}{k})$ 。那么边数的根号期望为 $\frac{\sum_{G \in G_{k}} \sqrt{| E |_{G}}}{| G_{k} |} \leq \sqrt{\frac{\sum_{G \in G_{k}} | E |_{G}}{| G_{k} |}} = \sqrt{\frac{m \cdot (\binom{n - 2}{k - 2})}{(\binom{n}{k})}} = O (\frac{\sqrt{m} k}{n})$ ，其中不等号应用了琴生不等式。

那么由于初始时我们打乱了点集，容易分析出第一部分期望点集大小和为 $O (\sum_{i = 1}^{⌈ \log n ⌉} 2^{i - 1} \cdot \frac{n}{2^{i - 1}} \cdot \frac{\sqrt{m} \frac{n}{2^{i - 1}}}{n}) = O (n \sqrt{m})$ 的。

如果不采用随机化，视实现不同分别可以卡到 $O (n \sqrt{m} \log n)$ 或 $O (n \sqrt{m \log n})$ 的上界。

第二部分分治寻找边。

引理 2：对于 $n_{1}, n_{2}, \dots, n_{k}, m_{1}, \dots, m_{k} > 0$ ，且 $m_{1} + \dots + m_{k} = m$ ，则 $\sum_{i = 1}^{n} n_{i} \sqrt{m_{i}} \leq \sqrt{(\sum_{i = 1}^{n} n_{i}^{2}) m}$ 。

证明：由拉格朗日乘数法，容易得到当 $m_{i} = \sqrt{\frac{n_{i}^{2} \cdot m}{\sum_{i = 1}^{n} n_{i}^{2}}}$ 时取极大值 $\sqrt{(\sum_{i = 1}^{n} n_{i}^{2}) m}$ 。

引理 3：在一对大小为 $O (| S |)$ 的独立集间分治寻找边，若找出了 $k$ 条，则点集大小和是 $O (| S | \sqrt{k})$ 的。

证明：分治寻找边的树形结构可以认为是一棵四叉树，其中第 $i$ 层至多有 $4^{i - 1}$ 个点，且每个点对应点集大小为 $O (\frac{| S |}{2^{i - 1}})$ 。考虑前 $⌈ l o g_{4} k ⌉$ 层，这部分点集大小和至多是 $\sum_{i = 1}^{⌈ l o g_{4} k ⌉} 4^{i - 1} \cdot \frac{| S |}{2^{i - 1}} = O (| S | \sqrt{k})$ 的。而对于后面的层，每条边对应路径的点集大小和至多是 $\sum_{i > ⌈ \log_{4} k ⌉} \frac{| S |}{2^{i - 1}} = O (\frac{| S |}{\sqrt{k}})$ 的。因此总点集大小和也是 $O (| S | \sqrt{k})$ 的。

那么考虑某一层，由于我们将 $L$ 和 $R$ 分别分成了 $O (\sqrt{m s})$ 个大小为 $O (\frac{| S |}{\sqrt{m s}})$ 的独立集，对于每一对有边的独立集，若其中有 $k$ 条边，对其分治点集大小和为 $O (\frac{| S | \sqrt{k}}{\sqrt{m s}})$ ，而仅有 $O (m s)$ 对，因此总点集大小和为 $O (| S | \sqrt{m^{'}})$ 。而所有点的 $\sum m^{'} = m$ ，那么所有点加起来的点集大小和为 $O (\sum_{i = 1}^{⌈ \log n ⌉} 2^{i - 1} \cdot \sqrt{{(\frac{n}{2^{i - 1}})}^{2} m}) = O (n \sqrt{m})$ 。

那么第二部分点集大小和就是 $O (n \sqrt{m})$ 的。

那么整个算法的期望点集大小和就是 $O (n \sqrt{m})$ 的。

期望得分 $100$ 分。

算法四

我们也可以给出一个渐进意义下相同的确定性算法。

考虑将分治的过程改为合并，令一个点集 $| S |$ 的权值为 $| S | + m s$ ，即点集大小加上点集内部边数。求一个哈夫曼树，每次选择两个权值和最小的点集合并，合并过程同算法三。

由于每个点被连续合并两次后，所在点集权值至少加倍，而点集总权值是 $n + m$ ，因此哈夫曼树深度是 $O (\log n)$ 的。那么类似算法三的分析，询问次数显然还是 $O (m \log n)$ ，且第二部分点集大小和显然还是 $O (n \sqrt{m})$ 。考虑对第一部分点集大小和换一个方式分析，每个点到根路径的 $\sqrt{m s}$ 之和放大为 $\sqrt{| S | + m s}$ 之和，这不超过 $2 \sum_{i \geq 0} \sqrt{\frac{n + m}{2^{i}}} = O (\sqrt{n + m}) = O (\sqrt{m})$ ，因此总点集大小和之和仍是 $O (n \sqrt{m})$ 的。

期望得分 $100$ 分，由于算法常数问题未必可以通过。

算法 X

由于数据范围问题，各种复杂度不一的算法均可能可以通过。

新年的军队

Idea, data, std, solution from EntropyIncreaser

简明题意

对于全体满足 $p_{i} > p_{i + 1}$ 的位置恰有 $m$ 个的 $n$ 阶排列，计算 $p_{k}$ 的分布。

算法一

使用著名的 next_permutation 枚举所有排列。

期望得分 $5$ 。

算法二

我们考虑 DP，设 $f (n, m, l)$ 表示对于 $(n, m)$ 来说， $p_{n}$ 的分布。那么每次考虑在结尾插入一个元素，可以通过前缀和优化转移，每个状态可以 $Θ (1)$ 得到答案。接下来对于 $p_{k}$ 的分布的计算，只需要拆成前面一个 $k$ 长度的排列和后面一个 $n - k + 1$ 长度的排列，枚举 $p_{k}$ 分布在其中的位置，以及两边大于号的数量即可。

时间复杂度 $Θ (n^{3})$ ，期望得分 $20$ 。

问题转化

为了方便刻画排列的性质，我们首先需要将问题进行适当的变换。考虑将问题进行下述改写：

对于全体满足 $α_{i} > α_{i + 1}$ 的位置恰有 $m$ 个的实数数列 $α_{1}, \dots, α_{n}$ ，计算 $α_{k}$ 的分布。其中每个 $α_{i}$ 在 $[0, 1]$ 上均匀分布。

由对称性可知，按照 $α$ 的排名分配的排列，每个排列都是等概率出现的。

那么我们在考察其中一个特定实数的分布的时候，用类似概率密度函数的工具来刻画是较为恰当的。如果一个 $n$ 阶排列中 $α_{k}$ 的排名是 $j$ ，那么其贡献的概率密度无非就是 $\frac{x^{j - 1} (1 - x)^{n - j}}{(j - 1)! (n - j)!}$ 这是因为当 $α_{k} = x$ 时，有 $j - 1$ 个数小于其的概率各是 $x$ ，然后他们有 $(j - 1)!$ 种排列方法，大于其的数情况类似。

转化为概率密度的好处在于，我们可以轻松地刻画问题中出现的约束关系，设原先的概率密度函数为 $f (x)$ ，那么有：

添加实数 $α_{n + 1}$ 要求其 $> α_{k}$ ，那么新的关于 $α_{n + 1}$ 的概率密度无非就是 $\int_{0}^{x} f (t) d t$ 。
对称地，若要求 $< α_{k}$ ，那么新的关于 $α_{n + 1}$ 的概率密度就是 $\int_{x}^{1} f (t) d t$ 。
又有实数 $β_{1}, \dots, β_{m}$ 关于 $β_{j}$ 的概率密度 $g (x)$ ，增添要求 $α_{k} = β_{j}$ ，此时 $α_{k}$ 的概率密度函数就是 $f (x) g (x)$ 。

注意到概率密度函数也是个多项式，设原排列中 $p$ 特定位置为 $k$ 的方案数为 $a_{k}$ ，那么我们就给出了转化关系： $f (x) = \sum_{k = 0}^{n - 1} f_{k} x^{k} = \sum_{k = 0}^{n - 1} a_{k} \frac{x^{k} (1 - x)^{n - 1 - k}}{k! (n - 1 - k)!}$ 因此，不难得到其反演： $\sum_{k = 0}^{n - 1} \frac{a_{k}}{k! (n - 1 - k)!} x^{k} = \sum_{k = 0}^{n - 1} f_{k} x^{k} (1 + x)^{n - 1 - k}$ 接下来，我们可以开始讨论怎么解决这个问题了。

算法三

设 $F (u, v, t)$ 表示一个排列，用 $u$ 计量 $" < "$ 的数量，用 $v$ 计量 $" > "$ 的数量，用 $t$ 计量概率密度，此时排列末尾的分布。立即列出方程 $F (t) = 1 + u \int_{0}^{t} F (τ) d τ + v \int_{t}^{1} F (τ) d τ$ 进行微分，可得 $F^{'} = (u - v) F$ 众所周知，这个微分方程的解是 $F (t) = C e^{(u - v) t}$ 但 $C$ 是包含 $u, v$ 项的，我们需要定出其形式。将原式带入 $t = 0, 1$ 的情况，设 $I = \int_{0}^{1} F (t) d t$ ，可得 $\begin{aligned} 1 + v I & = C \\ 1 + u I & = C e^{u - v} \\ C & = \frac{u - v}{u - v e^{u - v}} \\ F & = \frac{(u - v) e^{(u - v) t}}{u - v e^{u - v}} \end{aligned}$ 由于接下来要把两边粘起来，大小号是反过来的。

我们接下来让 $x$ 计量边数， $y$ 计量 $" > "$ 的数量。对于左侧，我们需要令 $u = x, v = x y$ ，对于右侧，我们需要令 $u = x y, v = x$ 。则有 $\begin{aligned} L & = \frac{(1 - y) e^{x (1 - y) t}}{(1 - y e^{x (1 - y)})} \\ R & = \frac{(y - 1) e^{x (y - 1) t}}{(y - e^{x (y - 1)})} \\ = \frac{(1 - y) e^{x (y - 1) (t - 1)}}{(1 - y e^{x (1 - y)})} \end{aligned}$ 设 $n_{1} = k - 1, n_{2} = n - k$ ，我们需要提取 $[x^{n_{1}}] L$ 和 $[x^{n_{2}}] R$ ，也就有 $\begin{aligned} [x^{n}] L & = (1 - y)^{n + 1} [x^{n}] \frac{e^{x t}}{1 - y e^{x}} \\ = (1 - y)^{n + 1} \sum_{j \geq 0} y^{j} \frac{(t + j)^{n}}{n!} \\ [x^{n}] R & = (1 - y)^{n + 1} [x^{n}] \frac{e^{x (1 - t)}}{1 - y e^{x}} \\ = (1 - y)^{n + 1} \sum_{j \geq 0} y^{j} \frac{(j + 1 - t)^{n}}{n!} \end{aligned}$ 计算乘积。 $\begin{aligned} ([x^{n_{1}}] L) \cdot ([x^{n_{2}}] R) \\ = \frac{1}{n_{1}! n_{2}!} (1 - y)^{n_{1} + n_{2} + 2} (\sum_{j \geq 0} y^{j} (t + j)^{n_{1}}) (\sum_{j \geq 0} y^{j} ((j + 1) - t)^{n_{2}}) \end{aligned}$ 我们考虑将结果这个 $f (t)$ 多项式插出 $0, \dots, n$ 的点值。

我们发现对于 $u^{n_{1}} \cdot v^{n_{2}}$ ，它会以 $[y^{m}] (1 - y)^{n + 2} y^{u + v - 1}$ 的贡献给满足 $t \in [1 - v, u]$ 的所有 $f (t)$ 。我们不妨做一个差分，就将所有 $u^{n_{1}} \cdot v^{n_{2}}$ 以 $[y^{m}] (1 - y)^{n + 2} y^{u + v - 1}$ 的 $- 1$ 贡献给 $t = u + 1$ ， $+ 1$ 贡献给 $t = 1 - v$ 。这是两个分别都是卷积。因此通过两次卷积就可以算出 $f (t)$ 的连续点值了。

复杂度 $Θ (n \log^{2} n)$ ，期望得分 $70 \sim 100$ ，取决于实现的常数差异。

算法四

插出点值这个过程其实并不是那么必要，我们考虑怎么直接计算系数。首先观察我们所求的和式 $\begin{aligned} \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} [y^{m}] (1 - y)^{n + 1} \sum_{i \geq 0} \sum_{j \geq 0} y^{i + j} (t + i)^{n_{1}} (t - (j + 1))^{n_{2}} \\ = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{s = 0}^{m} ([y^{m}] (1 - y)^{n + 1} y^{s}) \sum_{i = 0}^{s} (t + i)^{n_{1}} (t + i - (s + 1))^{n_{2}} \end{aligned}$ 里层的和是一个区间求和的形式（这和插值的前面步骤是一致的），我们考虑拆成正方向的无穷和 $\sum_{i + 1}$ 加上一个差分 $Δ_{s + 1} f (t) = f (t) - f (t + s + 1)$ 。设 $f_{s} = ([y^{m}] (1 - y)^{n + 1} y^{s})$ ，就有 $\begin{aligned} = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{s = 0}^{m} f_{s} Δ_{s + 1} (\sum_{i +} (t + i)^{n_{1}} (t + i - (s + 1))^{n_{2}}) \\ = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{s = 0}^{m} f_{s} (\sum_{i +} Δ_{s + 1} (t + i)^{n_{1}} (t + i - (s + 1))^{n_{2}}) + C \end{aligned}$ 我们这里将 $Δ$ 换到里面之后，无穷和的常数项其实就没法确定了。

一个常数小的计算 $C$ 的方法是注意到常数项在变换后对数列的影响恰好是给所有数加上一个量，而我们知道所有数的和必然是欧拉数 $⟨ \binom{n}{m} ⟩$ ，所以就很容易修正了。 $\begin{aligned} = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{i +} (\sum_{s = 0}^{m} f_{s} Δ_{s + 1} (t + i)^{n_{1}} (t + i - (s + 1))^{n_{2}}) + C \\ = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{i +} (\sum_{s = 0}^{m} f_{s} [(t + i)^{n_{1}} (t + i - (s + 1))^{n_{2}} - (t + i + (s + 1))^{n_{1}} (t + i)^{n_{2}}]) + C \end{aligned}$ 根据 Taylor 公式，我们知道 $f (t + c) = e^{c D} f (t)$ ，其中 $D$ 是对 $t$ 的求导算子。因而不妨设 $F (x) = \sum_{s} f_{s} x^{s + 1}$ ，就有 $\begin{aligned} = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \sum_{i +} ((t + i)^{n_{1}} F (e^{- D}) (t + i)^{n_{2}} - (t + i)^{n_{2}} F (e^{D}) (t + i)^{n_{1}}) + C \\ = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} Σ [(t^{n_{1}} F (e^{- D}) t^{n_{2}} - t^{n_{2}} F (e^{D}) t^{n_{1}})] + C \\ = \frac{(- 1)^{n_{2}}}{n_{1}! n_{2}!} \int B (D) [t^{n_{1}} F (e^{- D}) t^{n_{2}} - t^{n_{2}} F (e^{D}) t^{n_{1}}] + C, B (t) = \frac{t}{1 - e^{t}} \end{aligned}$ Bernoulli 数的使用是众所周知的，我们考虑如何快速计算 $F (e^{x})$ ，这需要考虑 $F (x)$ 满足的微分方程。 $\begin{aligned} F (x) & = \sum_{i = 0}^{m} (\binom{n + 1}{m - i}) (- 1)^{m - i} x^{i + 1} \\ = x f (x) \\ (n - m + 1 + i) f_{i} & = - (m - i + 1) f_{i - 1} + [i = 0] C \\ (n - m + 1) f (x) + x f^{'} (x) & = - m x f (x) + x^{2} f^{'} (x) + C \end{aligned}$ 令 $G (x) = F (e^{x}) = e^{x} g (x)$ ，可得 $\begin{aligned} (n + 1 - m + m e^{x}) g (x) + (1 - e^{x}) g^{'} (x) & = C \\ ((n - m) e^{- x} + m + 1) G + (e^{- x} - 1) G^{'} & = C \end{aligned}$ 我们可以通过半在线卷积的方法进行计算，时间复杂度 $O (\frac{n \log^{2} n}{\log \log n})$ 。预计得分 $100$ 。

虽然数据范围是 $5 \times 10^{5}$ ，但是半在线卷积还是很快的，胡写的标程只跑了 $1.2 s$ 。

算法五

这是一种与算法四殊途同归的推导。我们先不急着提取系数，考虑将两边的总变数写成 $p, q$ ，那么乘起来就是要提取 $(1 - y)^{2} \frac{e^{p t (1 - y) + q (1 - t) (1 - y)}}{(1 - y e^{p (1 - y)}) (1 - y e^{q (1 - y)})}$ 的 $[y^{m} p^{n_{1}} q^{n_{2}}]$ 。首先可以对 $p, q$ 做换元，提出来 $(1 - y)$ 的幂，就变成了 $(1 - y)^{n + 1} \frac{e^{p t + q (1 - t)}}{(1 - y e^{p}) (1 - y e^{q})}$ 我们对其施**分式分解**，即得 $(1 - y)^{n + 1} e^{p t + q (1 - t)} \frac{1}{e^{p} - e^{q}} (\frac{e^{p}}{1 - y e^{p}} - \frac{e^{q}}{1 - y e^{q}})$ 但是 $e^{p} - e^{q}$ 的倒数在计算上的意义是令人困惑的，但是我们若给上式对 $t$ 求导，可得 $\begin{aligned} (1 - y)^{n + 1} e^{p t + q (1 - t)} \frac{p - q}{e^{p} - e^{q}} (\frac{e^{p}}{1 - y e^{p}} - \frac{e^{q}}{1 - y e^{q}}) \\ = (1 - y)^{n + 1} e^{p t + q (1 - t)} \frac{(p - q) e^{- q}}{e^{p - q} - 1} (\frac{e^{p}}{1 - y e^{p}} - \frac{e^{q}}{1 - y e^{q}}) \\ = (1 - y)^{n + 1} e^{(p - q) t} B (p - q) (\frac{e^{p}}{1 - y e^{p}} - \frac{e^{q}}{1 - y e^{q}}), B (x) = \frac{t}{e^{t} - 1} \end{aligned}$ 因此我们对 $y$ 提取系数，就出现了算法四中的 $G (x) = F (e^{x})$ ： $e^{(p - q) t} B (p - q) (G (p) - G (q))$ 以 $e^{(p - q) t} B (p - q) G (p)$ 为例，换元为 $e^{p (1 - r) t} B (p (1 - r)) G (p)$ ，提取 $[p^{n - 1} r^{n_{2}}]$ ，展开可得 $\begin{aligned} \sum_{j} ([p^{n - 1 - j}] G (p)) ([r^{n_{2}}] (1 - r)^{j}) [p^{j}] B (p) e^{p t} \\ = \sum_{j} Q_{n - 1 - j} [p^{j}] B (p) e^{p t}, Q (p) = \sum_{j} ([p^{n - 1 - j}] G (p)) ([r^{n_{2}}] (1 - r)^{j}) p^{j} \\ = [p^{n - 1}] Q (p) B (p) e^{p t} \\ = \sum_{j} \frac{t^{j}}{j!} [p^{n - 1 - j}] Q (p) B (p) \end{aligned}$ 这种做法的实际实现几乎是和算法四一致的。

新年的挑战

Idea from rushcheyo

Checker 有两版，分别由 rushcheyo 和 vfleaking 完成

Task 1, 3: std, solution from rushcheyo

Task 2: std, solution from skip2004

本题准备时间实在太短，主要的精力都花在搭建嘿嘿计算机上了，题目本身内容不是很有趣，再道歉一次。

任务一：排序

由于时间仓促，我没实现任意一种暴力。从比赛现场来看，堆排序和归并排序都可以拿到一定的分数。在此基础上和其他任务一样把分治叉数增大到 $Θ (w)$ 就可以优化一个 $\log w$ 因子达到接近满分。

std 的做法是，首先将数组随机 shuffle，然后一个一个把元素插进最 naive 的 BST，最后先序遍历 BST 即可。每次插入的时候要找到插入位置，需要 $O (\log n)$ 次读，然后插结点仅需 $O (1)$ 次写，于是期望时间复杂度为 $O (n w + n \log n)$ 。

任务二：维护前缀和

首先如果我们不知道下标是多少，我们只能在内部实现数据结构，这是很低效的，需要大量的判断语句，因此我们考虑把下标转移到外部。

我们可以用好多好多 CMP 下标和 JMP 来把程序分成 $n$ 个部分，每个部分都是下标确定时候要做的操作。

然后使用树状数组来进行维护，我们求出已知下标时需要访问的位置，直接实现即可。

但是由于修改复杂度较高，所以我们可以把树状数组的叉数提高至 $Θ (w)$ ，这样复杂度为 $O (n w \log_{w} n)$ 。

事实上，这里层数不大，类似于分块，而分块有这样一种常数优化的技巧：询问一个块内区间信息，用大块信息减去其余信息来求解它。

我们记 $s_{i}$ 为 $\sum_{x = 0}^{i} a_{x}$ 。容易发现一个区间 $[l, r]$ 可以用一条指令的代价由 $s_{l - 1}$ 算出 $s_{r}$ 或者由 $s_{r}$ 算出 $s_{l - 1}$ ，同时这个区间内元素发生修改时它需要被更新。因此如果我们知道所有这些区间，只需要连边跑最短路就可以知道怎么最快求解一个 $s_{i}$ 。

这里 std 选用了 $[i, i], [32 i, 32 i + 31], [928 i, 928 i + 927]$ 这些区间，得到了一个还不错的解。

任务三：多项式乘法

算法一

这不是裸的 FFT 吗？容我抄个 FFT 板子，改成 hei++ 语言，一发 AC！出题人可真 sb。

本题的指令集中间进行了一次大更换，在迁移老版 std 时我忘记了寄存器数量达到了 $32$ 之多，导致 task 3 的 std 浪费了一些拷贝的时间，致使直接的 FFT 代码通过了，非常非常抱歉！选手赛后做题时可认为本任务 $u = 2363007$ 。

算法二

与任务二中的思想类似，我们将 FFT 的叉数增大到 $Θ (w)$ ，本题不妨设叉数 $k = 16$ 。

$k$ 叉 FFT 的做法是，先将多项式 $f$ 按 $mod k$ 分类： $f (x) = \sum_{i = 0}^{k - 1} x^{i} f_{i} (x^{k})$ ，于是有：

$f (ω_{n}^{i + \frac{n}{k} p}) = \sum_{j = 0}^{k - 1} ω_{n}^{(i + \frac{n}{k} p) j} f_{j} (ω_{n}^{i k}) = \sum_{j = 0}^{k - 1} ω_{n}^{(i + \frac{n}{k} p) j} f_{j} (ω_{n / k}^{i})$

这样的做法时间复杂度是 $O (n k \log_{k} n)$ 的，但只需要 $O (n \log_{k} n)$ 次写操作，毕竟最内层只有算术运算，于是总复杂度为 $O (n w \frac{\log n}{\log w})$ ，比起裸暴力优化了 $O (\log w)$ 。

然后和经典的 FFT 类似，我们可以在 $k$ 进制下 reverse bits，就能把程序转成非递归了。当然这不是必要的。

rushcheyo的博客

博客