UOJ Round #3 题解

核聚变反应强度

算法一

对于 $n = 1$ 的数据，就是求一个数次大的约数。

众所周知一个数 $x$ 的约数是成对出现的（ $d$ 、 $\frac{x}{d}$ ），其中总有一个不超过 $\sqrt{x}$ 。所以从 $1$ 到 $\sqrt{a_{1}}$ 地枚举 $d$ 就能找出所有 $a_{1}$ 的约数了。排序输出次大的即可。

复杂度： $O (\sqrt{a})$

算法二

先找出 $a_{1}$ 的所有约数，然后枚举 $i$ ， $sgcd (a_{1}, a_{i})$ 显然也是 $a_{1}$ 的约数，所以枚举 $a_{1}$ 的所有约数，找到是 $a_{i}$ 约数的次大的即可。

复杂度： $O (n \sqrt{a})$

算法三

考虑分解质因子后：

$a = p_{1}^{x_{1}} p_{2}^{x_{2}} . . . p_{m}^{x_{m}}$

$b = p_{1}^{y_{1}} p_{2}^{y_{2}} . . . p_{m}^{y_{m}}$

则： $gcd (a, b) = p_{1}^{min (x_{1}, y_{1})} p_{2}^{min (x_{2}, y_{2})} . . . p_{m}^{min (x_{m}, y_{m})}$

我们发现， $a$ 和 $b$ 的公约数都一定是 $gcd (a, b)$ 的约数。那么为了得到次大公约数，只需求出 $gcd (a, b)$ ，再除去一个最小的公共质因子即可。

对 $a_{1}$ 用 $O (\sqrt{a_{1}})$ 的时间分解得到 $O (\log (a_{1}))$ 个质因数，每次对于 $a_{i}$ ，先求出 $g = gcd (a_{1}, a_{i})$ ，然后枚举 $a_{1}$ 的每个质因数，找到最小的能整除 $g$ 那个，设其为 $p$ ， $g / p$ 即为所求。（不存在则为输出 $- 1$ ）

复杂度： $O (\sqrt{a} + n \log (a))$

一个骗分算法

考虑算法二，我们预先对 $a_{1}$ 的约数们排好序，然后枚举 $i$ ，从约数表里每次二分到 $gcd (a_{1}, a_{i})$ 所在位置，再往前枚举，找到第一个能整除 $a_{i}$ 的即为次大公约数。

虽然复杂度不靠谱，但是对于 $a_{i} \leq 10^{12}$ 的范围实际运行速度十分优秀。需要构造针对的数据才能卡住。

还有另一个骗分算法，求出 $gcd$ 然后暴力枚举最小质因子。好多人写这个啊……你们都没意识到复杂度不对么……放你们一马给了 80 分。

（有这种闲心的为啥不写正解啊，你们考虑过 maker 的感受吗！QAQ）

铀仓库

算法一

我们先来证明几个显然的结论。

结论一：小O的行动一定是，每次看准一个箱子，从 $s$ 跑过去拿起来，然后直接搬回 $s$ 。

首先，小O一定不会把一个箱子搬到离 $s$ 更远的地方。其次我们考虑，如果小O进行了这样的动作：从 $a$ 搬到 $b$ 、从 $c$ 搬到 $d$ ，其中 $a < b < c < d < s$ ，那么等价于从 $a$ 搬到 $d$ ，从 $c$ 搬到 $b$ ，显然干了多余的事。

结论二：起始位置 $s$ 一定有箱子。

考虑确定了 $s$ ，一定是搬来前若干近的箱子，也就一定是连续的一段，所耗时间为距离和的两倍。我们知道，给定数轴上若干个点，选一个坐标最小化每个点到它的距离和，那么一定是选这些点坐标中的中位数（调整法可证）。

说了一大堆废话，我们得到一个暴力做法。枚举 $s$ ，每次拿来一个最近的即可。

复杂度： $O (n^{2} T)$

算法二

枚举 $s$ ，由于是取前若干近的过来，我们二分取的最远的在哪。如果 $x_{i} = i$ 那么直接可以 $O (1)$ 确定左右端点，否则我们需要再一次二分确定左右端点。

复杂度： $O (n \log n \log X)$ ， $X$ 表示坐标范围。

算法三

先二分答案，于是问题变成了：求叠到 $K$ 个箱子所需的最短时间。

由于取的一定是连续的一段，设其为 $[l, r]$ ，若 $a_{i} = 1$ ，我们直接从左到右枚举 $s$ ，此时由于左边的越来越远，右边的越来越近， $l 、 r$ 一定是非降的。所以，每次 $s$ 右移的时候，判断 $r + 1$ 处是否比 $l$ 近，如果是就一直替换，直到不是为止。

移动左右端点的同时顺便维护一下距离和就好了。

这样的复杂度是 $O (n + Σ a_{i})$ 的，还是不能通过全部数据。

加一个小优化就好了。把每个位置的 $a_{i}$ 个箱子想象成横着紧贴成一排，称为一组箱子，那么每次我们移动左右端点 $l 、 r$ 的时候，事实上是干了很多重复的事情的。

如果 $l$ 、 $r$ 所在箱子组都不变，那么会一直进行替换，直到某个端点换组。所以在每次替换的时候，直接加速到某个端点换组的时刻即可。

复杂度： $O (n \log X)$

链式反应

算法一

按照题意进行爆搜，可以通过第一个测试点获得 10 分。

算法二

我们得思考一下这题题意到底是啥意思。其实说，一棵有标号的树，编号满足堆的性质，对于儿子方向每个结点有两条红色边， $c$ 条黄色边， $c$ 属于集合 $A$ ，统计方案数。

所以我们用 $f [n]$ 表示 $n$ 个结点的这个样子的树的方案数。然后要么 $1$ 号点没有进行核裂变，此时必有 $n = 1$ 且 $f [n] = 1$ 。要么 $1$ 号结点进行了核裂变，此时我们枚举两个中子打中的结点的子树的大小 $j, k$ ，剩下的就是被破坏死光打中的，于是要满足 $i - 1 - j - k \in A$ 。然后考虑两个中子打中的结点的子树，我们先选出它们的编号，方案数是 $(\binom{i - 1}{j}) \cdot (\binom{i - 1 - j}{k})$ ，然后我们就可以安全地把这两棵子树的结点都重标号，方案数自然是 $f [j]$ 和 $f [k]$ 。所以我们把这些杂八事综合起来就得到了一个简单的DP： $f [i] = \sum_{j} \sum_{k} (\binom{i - 1}{j}) \cdot (\binom{i - 1 - j}{k}) \cdot f [j] \cdot f [k]$ 。这里的 $j, k$ 要满足 $i - 1 - j - k \in A$ 。直接暴力递推就得到了一个 $O (n^{3})$ 的算法。

什么，过不了样例？当然过不了样例了，因为有重复计数。那两个中子是等价的，一个方案自然会被统计了两遍，只要把 DP 方程除以 $2$ 就好了。

可以通过前 $4$ 个测试点获得 40 分。

算法三

其实只要在算法二基础上优化就行了。我们仔细观察式子： $(\binom{i - 1}{j}) \cdot (\binom{i - 1 - j}{k}) = \frac{(i - 1)!}{j! k! (i - j - k - 1)!}$ 。有四个部分，第一个只跟 $i$ 有关，第二个只跟 $j$ 有关，第三个只跟 $k$ 有关，第四个只跟 $i - j - k - 1$ 有关。所以我们可以递推一个 $g [i] = \sum_{k} \frac{f [k]}{k!} \frac{f [i - k]}{(i - k)!}$ 。然后递推 $f [i]$ 时我们枚举 $j + k$ 的和 $s$ ，那么直接读取 $g [s]$ 的值，然后剩下的部分就是一些跟 $i$ 和 $s$ 有关的了。

好像说得挺意识流的，具体就是： $f [i] = \frac{1}{2} \sum_{s} g [s] \cdot \frac{(i - 1)!}{(i - s - 1)!}$ 。 $s$ 要满足 $i - s - 1 \in A$ 。

可以通过前 $6$ 个测试点获得 60 分。

算法四

再观察一下式子，搞个数组 $a$ ，其中如果 $i \in A$ 则 $a_{i} = \frac{1}{i!}$ ，否则为 $0$ 。然后原递推式的右边的第 $i$ 项其实就是 $g$ 跟 $a$ 的卷积的第 $i - 1$ 项然后再乘以 $(i - 1)!$ 。然后其实 $g$ 本身也是个卷积，就是 $\frac{f [i]}{i!}$ 这个数列的平方。

我们可以使用分治。每次分治一个区间 $[l, r]$ ，我们找出中点 $m$ ，然后递归 $[l, m]$ ，然后求出 $[l, m]$ 对 $[m + 1, r]$ 的贡献，再递归右边。

考虑左边对右边的贡献，“ $(\binom{i - 1}{j}) \cdot (\binom{i - 1 - j}{k}) \cdot f [j] \cdot f [k]$ ” 中，左边可能作为 $f [j]$ 也可能作为 $f [k]$ 出现，也可能都出现。我们只要考虑这几种情况然后分别进行 FFT 就行了。看起来要和整个 $a$ 或者 $f$ 进行卷积？其实不然，只用取出一个长度为分治时的区间的长度的前缀就可以了。

时间复杂度 $O (n \log^{2} n)$ 。可以通过前 $9$ 个测试点获得 90 分。常数小的话应该能过。

算法五

以下内容需要一点微积分知识……如果是微积分恐惧症……您还是看算法四加卡常数吧～我还是很良心的没让所有人都非得用算法五才能AC～

嗯，既然都发现是卷积了，那么肯定少不了生成函数。我们记 $\frac{f [i]}{i!}$ 的生成函数为 $x (t)$ ， $a_{i}$ 的生成函数为 $a (t)$ ，那么生成函数就要满足： $x^{'} (t) = \frac{1}{2} a (t) x^{2} (t) + 1$ 。

拨一下 mathematica 就会发现它解不出来这个微分方程，所以只有自力更生了。

首先科普下一般来说应该怎么解一个多项式方程（更严谨地说这里应该是形式幂级数）。假设 $x (t)$ 满足 $f (x (t)) = 0$ ，那么我们先求出 $0$ 次项的系数，然后每次倍增。也就是说每次我们有一个多项式 $x_{n}$ 满足 $x_{n}$ 和 $x$ 的前 $n$ 项系数是一样的，我们记为 $x \equiv x_{n} (\mod t^{n})$ ，然后我们要求出 $x_{2 n}$ 满足 $x \equiv x_{2 n} (\mod t^{2 n})$ 。使用泰勒展开可以得到:

$0 = f (x_{2 n}) = f (x_{n}) + f^{'} (x_{n}) (x_{2 n} - x_{n}) + \frac{1}{2} f^{″} (x_{n}) (x_{2 n} - x_{n})^{2} + \dots$

注意到如果只考虑前 $2 n$ 项，那么就可以去掉二次项及之后的项然后解出：

$x_{2 n} \equiv x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} (\mod t^{2 n})$

由于 $T (n) = T (n / 2) + O (n \log n)$ 解出来是 $T (n) = O (n \log n)$ ，所以只要能足够快地把 $x$ 带入 $f (x)$ ，那么就能 $O (n \log n)$ 解方程。（当然需要 FFT 做多项式乘法）

什么这里有个除法？我们可以利用牛顿迭代求出一个形式幂级数的乘法逆元，于是就能做除法了。

于是微分方程也可以如法炮制，假设有个这样的一阶微分方程：

$\frac{d}{d t} x = f (x)$

我们还是老样子：

$\begin{array}{rcl} \frac{d}{d t} x_{2 n} & \equiv & f (x_{n}) + f^{'} (x_{n}) \cdot (x_{2 n} - x_{n}) (\mod t^{2 n}) \\ \equiv & f (x_{n}) + f^{'} (x_{n}) \cdot x_{2 n} - f^{'} (x_{n}) \cdot x_{n} (\mod t^{2 n}) \end{array}$

所以问题变成了这玩意儿怎么解……而这玩意儿其实很好解……我们两边同时乘以 $e^{- \int f^{'} (x_{n}) d t}$ （囧……由于公式嵌套过多，排版已经开始混乱了），记作 $r$ ：

$\begin{array}{rcl} \frac{d}{d t} x_{2 n} \cdot r & \equiv & (f (x_{n}) - f^{'} (x_{n}) \cdot x_{n}) \cdot r + f^{'} (x_{n}) \cdot x_{2 n} \cdot r (\mod t^{2 n}) \\ \frac{d}{d t} (x_{2 n} \cdot r) & \equiv & (f (x_{n}) - f^{'} (x_{n}) \cdot x_{n}) \cdot r (\mod t^{2 n}) \end{array}$

然后只要把右边积分再除以 $r$ 就行了。

注意到虽然人类无法方便地给任意函数积分，但是给多项式求导和求积分简直易如反掌。所以唯一的难点在于 $r$ 怎么求。

好吧其实我几个月前 YY 到这里直接就弃疗了，后来翻了翻论文，知道了怎么求 $e^{x}$ 。由于 $e^{x}$ 的反函数是 $\ln (x)$ 而 $\ln (x)$ 对 $t$ 的导数是 $\frac{x^{'}}{x}$ ，所以 $\ln (x)$ 可以快速求，然后我们就可以进行牛顿迭代求 $\ln (x)$ 的反函数得到 $e^{x}$ 。