缩进优化

算法一

方便起见用 $/$ 表示整除，$X$ 表示最大的 $a_i$。

要最小化的就是 $\sum_{i=1}^{n} a_i / x + a_i \bmod x$。

枚举 $x$ 再暴力计算上式并更新答案，由于 $x$ 不超过 $X$，所以复杂度是 $O(nX)$。可以获得20分。

算法二

$a_i$ 相同的可以合并在一起，然后就得到了 $O(n + X^2)$ 的算法，结合算法一可以获得40分。

算法三

方便起见，我们换个角度，先给答案加上 $a_i$ 的和，再最大化“节约的代码”。

由于把 $x$ 个空格替换成一个TAB节约了 $x-1$ 的代码，令 $z_i$ 表示 $\sum_{i=1}^n {a_i/x}$，那么就是最大化 $(x-1)z_i$。

枚举每个 $a_i$ 考虑其对 $z$ 的贡献。由于 $a_i/x$ 至多只有 $\sqrt{a_i}$ 种不同取值，且每种取值对应的 $x$ 是连续一段，也就是对 $z$ 进行若干次区间加上一个值的操作，用点事件每次可以做到 $O(1)$。

最终复杂度是 $O(n \sqrt{X} + X)$。可以获得70分。

算法四

算法三其实把问题想复杂了。

我们对每个 $x$ 直接计算 $z_x$ 就好了：枚举 $a_i/x$ 的值 $t$，查询满足 $tx \le a_i < (t+1)x$ 的$i$的个数，然后给 $z_x$ 加上值和个数的积。注意 $a_i/x$ 的值只需枚举到 $X/x$。

我们统计 $c_x$ 表示 $a_i=x$ 的 $i$ 的个数，记录 $c$ 的前缀和以便查询区间和。

一个著名的性质是： \begin{equation} \sum_{k = 1}^{n}{\frac{1}{k}} = O(\log n) \end{equation}

所以我们就得到了一个 $O(X/1 + X/2 + X/3 + \dots + X/X)=O(X \log X)$的算法。可以获得100分。

只想说标程500B……考场上那么多人没A是个什么情况囧囧囧……

外星人

题目意思其实就是给出一个 $x$ 和 $n$ 个数 $a_i$，你需要得到一个排列 $p$，使得依次执行 $x = x \bmod a_{p_i} $ 后，$x$ 的值最大，求最后最大的 $x$ 值以及能得到这个 $x$ 这样的排列数对 $998244353$ 取模后的结果。

算法一

对于第1个测试点，范围超级小。于是我们可以枚举每一个可能的排列并且模拟。这样就可以获得 10 分。

算法二

考虑取模运算。一个非常基础的性质是：当 $x \geq a_i$ 时，$x \bmod a_i < a_i$。当 $x < a_i$ 时，$x \bmod a_i = x$。

假设我们有 $a_i > a_j$，当我们使用了 $a_j$ 使得 $x$ 变为 $x \bmod a_j$，此时一定有 $x \bmod a_j < a_i$。那么一旦我们用了 $a_j$ ，$a_i$操作将不可能再影响 $a_i$，从而我们可以将 $a$ 从大到小排序，然后从前往后考虑。

我们可以用dp。用 $f[i, j]$ 表示当前处理完第 $i$ 个外星人了，当前的 $x$ 为 $j$。转移显然：$f[i + 1, j \bmod a_{i+1}] = \max f[i, j]$。

这样做就在 $O(nx)$ 的时间内解决了第一问。配合算法一可以获得 46 分。

算法三

于是我们着手来解决第二问。我们可以用 $f[i, j, k]$ 表示当前已考虑完排列的第 $i$ 个位置，$x$ 的值为 $j$，还剩 $k$ 个外星人的手指数比 $j$ 大的最优解与方案数。

考虑第 $i$ 个位置应该填什么，有两种选择，一个是放一个有效的外星人，另一个是放一个无效的外星人。有效外星人即真正会让 $x$ 发生改变的外星人。注意现在 $x = j$，那么说明手指数小于等于 $j$ 的外星人一个都没有用过。所以我们可以从 $k$ 个剩下的外星人或者从手指数小于等于 $j$ 的外星人中选一个进行转移。

如果你最裸地写的话复杂度大约是 $O(n^4x)$，如果你做个前缀和来统计新增加的比 $x$ 大的外星人个数的话，就可以做到 $O(n^3x)$。

可以在算法二的基础上多通过2,3号测试点获得 58 分。

算法四

没错我相信你已经发现了，算法三的那个 $i$ 压根没有用上。它是来打酱油的？对就是打酱油的。所以去掉 $i$ 就可以把时间复杂度变为 $O(n^2x)$。

可以在算法三的基础上多通过4,5,6号测试点获得 76 分。当然我觉得这三个点 $n \leq 100$，$O(n^3x)$还是可以过的。算法三和算法四的技术含量其实差不太多，所以无所谓了。

算法五

没错我相信你已经发现了，算法四的那个 $k$ 简直就是惊天大酱油。

对，我们只需要 $f[j]$ 作为状态就够了。用 $f[j]$ 表示 $x = j$ 且只考虑手指数小于等于 $j$ 的外星人的情况下的最优解与方案数。

怎么转移呢？我们在手指数小于等于 $j$ 的外星人中选一个 $a_k$ 作为下一个发送信息的外星人，显然这个外星人一定是有效外星人。那么考虑手指数介于 $(j \bmod a_k, j]$ 的外星人，我们发现只要把他们随便插入到 $f[j \bmod a_k]$ 的最优解排列中去就可以了。这个显然可以用简单的组合数学解决。方案数即 $\frac{(N_j - 1)!}{N_{j \bmod a_k}!}$。其中 $N_c$ 表示手指数不超过 $c$ 的外星人个数。

只要预处理阶乘以及阶乘的逆元就可以做到 $O(nx)$。可以通过全部测试点获得 100 分。

跳蚤国王下江南

我们来看这场比赛的最难题——仙人掌上有源简单路径计数。

相信不少小朋友被第二题和第三题的模数吓着了，其实真正需要FFT的只有第三题。唔……以后UOJ Round的题都用这个模数吧，这样出FFT就没人发现了。

算法一

我送了超良心的20分大暴力。前两个点的数据范围超小，不过可能有人会被仙人掌吓着了忘记了普通图上这个问题是怎么做的。显然dfs搜出所有路径就好。

算法二

我们看到前5个点的数据范围只有 $1000$，我们只要稍微了解下如何处理仙人掌就可以用dp解决。

仙人掌其实有很强的树的感觉，毕竟任意两个不同的简单环的交集至多是一个结点而已。我们考虑 $1$ 号点，他有若干个“儿子”。不过这次不像树那样单纯了，一个儿子可能是一个结点，也可能是一个环。所谓儿子是环，就是说可能有穿过 $1$ 号点的环，我们认为这个环作为一个整体也是 $1$ 的儿子。

至于其它的结点，像树一样，我们不得不把与它相邻的点和环中，挑出一个作为父亲。所以有些结点的父亲是个环，有些结点的父亲是结点。比如 $1$ 的环儿子上的结点，我们都认为父亲是个环。我们定义环的父亲就是那个把这个环当作自己的儿子的那个点，环的儿子就是环上除环的父亲以外的点。

好那么说到这里仙人掌的树形结构貌似就很清楚了。我们可以从 $1$ 号点开始往下dfs，每次都找出自己的儿子，然后再从儿子那里递归下去。这个可以自己思考一下具体怎么写。我的方法是记录一个 dfs number 表示每个结点的访问时间，以及每个结点都定义父亲结点和母亲结点。如果结点的父亲是环，那么父亲结点和母亲结点分别是环上与之相邻的两个结点。如果结点的父亲是个结点，那么这个结点只有父亲结点，没有母亲结点（好吧“父亲”、“父亲结点”、“母亲结点”，这三个定义挺丑陋的。但是我也不知道怎么取名了。我这里说的父亲和父亲结点不是一个概念）。具体的dfs过程比较简单，可以自己想一想。

分辨清楚谁是自己的儿子之后，dp就很显然了。记 $f[v][l]$ 表示从 $v$ 往下走长度为 $l$ 的简单路径个数，然后扫 $v$ 的所有儿子，如果是结点那么就用 $f[u][l - 1]$ 更新，如果是个环就扫环的儿子，根据顺时针走的距离 $s_l$ 和逆时针走的距离 $s_r$，用 $f[u][l - s_l]$ 和 $f[u][l - s_r]$ 更新答案。

这样就可以通过前5个测试点获得50分。为了防止有人用极其暴力的方法处理仙人掌结点间的父子关系什么的，我留了一个 $n \leq 100$ 的测试点供不知道怎么处理仙人掌问题的小朋友乱搞。

详见 http://uoj.ac/submission/2263

算法三

注意6,7号测试点，仙人掌主体是一条链，剩下的是一些奇怪的边。由于是仙人掌，这些奇怪的边所对应的链上的区间一定是不相交的。考虑链的末尾的那个结点 $v$，如果我想求出从 $1$ 到 $v$ 的长度为 $l$ 的简单路长度，应该怎么做？没错，如果一条边没有被奇怪的边的区间覆盖我们就当成多项式 $x$，如果是一个长度为$s$的环我们就当作多项式 $x + x^{s - 1}$，然后把这些多项式乘起来，取 $x_l$ 前的系数就是答案。

这启发我们用分治进行解决。我们把环当作一个整体，这样我们就可以把原图看作一个边和环组成的序列。我们要对这个序列求出从第一个结点出发的简单路所对应的多项式 $f(x)$ 和从第一个结点出发到最后一个结点结束的简单路所对应的多项式 $g(x)$。

好，那么我们每次把序列劈成两半，求出左边的信息和右边的信息，然后拿左边的 $g(x)$ 乘以右边的 $f(x)$，再加上左边的 $f(x)$ 就得到了总体的 $f(x)$。至于总体的$g(x)$，把左边和右边的$g(x)$乘起来就行。如果序列分得不能再分，说明只剩了一条边或者一个环，这个显然可以轻松求出 $f(x)$ 和 $g(x)$。

使用FFT进行多项式乘法，可以做到每次 $O(n \log n)$。这样最底层长度为$l$的多项式对最终时间复杂度的贡献就是$O(l \log^2 n)$，所以我们就得到了 $O(n \log^2 n)$ 的算法。如果你不幸每次递归时用 $O(n \log^2 n)$ 来一次分治求出 $g(x)$……只能说你这样太暴力了，这样算法会变成 $O(n \log^3 n)$ 的。不过我经过常数优化亲测可过。

算法四

其实算法三对最终解法很有启发性。如果你链的情况只能用分治来做，想不出别的算法，那么对于任意的仙人掌，你肯定也只能用分治来做了。考虑链的情况的关键点在于把环看成一个整体，把整个图从某处割开。同样这个可以拓展，我们还记得树的点分治——每次找一个重心把树拆开，由于重心的神奇性质导致剩下的连通块每个都不超过原图大小的一半。

做树分治时候，每次我们找重心，即使得去掉这个结点后剩下的连通块大小最大的那个最小。对于仙人掌我们如法炮制，找一个结点，把和它相连的边都断了并且他在的每一个环上的边都要去掉（不去掉环上的其它结点）。这样找出连通块最大的最小作为重心。

然后别忘了我们是有根的仙人掌。去掉这个重心后会剩下若干个连通块，其中一个是与根结点在一起的，另一部分是自己的儿子们。如果重心的父亲是个环的话，那么还需要递归环上的其它儿子。利用算法三求 $g(x)$ 的那一部分，我们可以在 $O(n \log^2 n)$ 时间内求出根结点到重心（如果重心的父亲是个环那么由于要考虑环上其它的儿子，这种情况下应该是根结点到重心的父亲）的简单路径所对应的多项式 $g(x)$，然后把重心删了，递归根结点那边的连通块直接累加答案，分别递归其它连通块把答案加起来再乘以 $g(x)$ 也累加进答案。这样总时间复杂度就是 $O(n \log^3 n)$ 了，亲测在卡常数的情况下可以获得100分。

详见 http://uoj.ac/submission/2491

详见 http://uoj.ac/submission/6097

算法五

显然这个故事要是以 $O(n \log^3 n)$ 结尾就太不优美了。请注意，点分治本身也是分治，当你在点分治里再套个分治去求 $g(x)$ 时，是不是应该经过一下大脑思考？

由于点分治每次分割仙人掌后仙人掌大小减半，所以如果我们从根结点出发到我们现在要划分出去的重心 $C$ 来一次时空之旅的话，我们可以看到一副奇特的场景。我们从根结点出发往我当前的重心走，走着走着可以碰到未来删掉重心后根结点所在的连通块的重心，当我们经过这个重心后，我们知道由于是重心，我们的旅途大约已经走一半了。我们把时间调到这个重心被去掉之后，继续往下走，又会碰到一个未来要删掉的重心，此时我们知道我们的旅途已经走的四分之三了。我们再把时间调到这个重心被去掉之后。这样一直走下去，每次碰到一个重心，我们所在的仙人掌大小就减半，最终我们旅途终结的地方是我们的重心 $C$ 的父亲自己就是整棵仙人掌的时候了，然后自己就是重心，把自己去掉，世界清净了。

从这个过程中我们可以得到一个想法：假如我们保存旅途中相邻的重心之间的简单路径所对应的多项式，以及重心自己所对应的多项式，那么我们逆着旅游的顺序把他们乘起来就好了。这样为什么是 $O(n \log n)$ 的？因为 $T(n) = O(n \log n) + T(n / 2)$ 解出来就是 $T(n) = O(n \log n)$。

所以现在的问题就是怎么求相邻重心之间的简单路径所对应的多项式。其实时空之旅蕴含的意思很明显了，所谓相邻重心，真正当分治下去的时候，当我要删掉一个仙人掌的重心，这个仙人掌的根的位置几乎就是上一个重心的位置。所以在那个重心感受到的“相邻重心”就是从重心到根的简单路径对应的多项式，也就是原问题。

UPD：实际实现中，如果重心的父亲是个环，那么应该求从根到这个环父亲那里的多项式。所以如果重心的父亲是个环那么我们令 $s$ 为重心的父亲环的父亲，否则为重心本身。我们每次要求的是根到 $s$ 的多项式，这显然可以从 $s$ 出发（如果重心的父亲不是环则从 $s$ 的父亲出发）不断往上跳，每次跳到这个结构的 $s$ 所在处把多项式暴力乘起来，然后再根据存好的 $s$ 到根的多项式跳到上一层分治的时刻，如此往复。

所以只要每次找到重心后，先递归根结点所在的连通块，然后不断往上跳，就可以求出根结点到 $s$ 的简单路径所对应的多项式，然后我们把它保存下来供以后使用。其余部分与算法四相同。这样我们就得到了 $O(n \log^2 n)$ 的优美算法。

这样子就可以轻松通过所有测试点获得100分了。

详见 http://uoj.ac/submission/2492 详见 http://uoj.ac/submission/6096

唔……感觉这个算法描述起来挺绕舌头的。如果没看懂的话在下面回复下，我进一步解释下。