士兵调度

from zx2003

子任务一

构造方法非常多。

一个简单的办法是，对于所有 $n$ 名士兵，将第 $i$ 个士兵的坐标设为 $(i,i)$。然后对于所有 $m=n-1$ 次移动，第 $i$ 次移动将第 $i+1$ 个士兵挪到第 $1$ 行。容易发现这样总的变化次数恰好为 $n$。

子任务二

构造方法仍然非常多。这里给出一种常数较优的做法。

取一个 $400 \times 500$ 的棋盘，将其黑白染色，并在所有黑格上放上士兵。之后每次操作将相邻列的士兵合并起来，这样所有 $n$ 个士兵所属的分组都会变化恰好一次，并且操作步数只需 $250$。

子任务三，四

我们分析下这个问题的性质。

对于一组 $y$ 坐标相同的士兵，设其中有 $a$ 人分组为第二组。则按照分组规则，这些士兵所属的 $x$ 坐标上一定分别有不少于 $a$ 名士兵。故而，$a$ 一定不超过 $\sqrt{n}$。对于 $x$ 坐标进行同样分析，我们就知道了每次操作后分组变化次数一定不超过 $2\sqrt{n}$。

对于总的操作次数，我们可以得到一个更好的上界。注意到每次操作时合并的两行中，较小的那一行贡献的变化次数可以用启发式合并的来分析，这一部分的步数总和是 $n\log n$。所以总的变化次数的界为 $m\sqrt{n}+n\log{n}+O(n+m)$。

下面给出标算的构造。

我们将操作分为若干轮执行。对于第 $T$ 轮，我们需要将点集由 $(T-1) \times (T-1)$ 的正方形增加一行一列变为 $T \times T$ 的正方形，这样在该轮中所有 $(T-1) \times (T-1)$ 个原正方形中的点的分组都会变化一次。我们可以现在平面远处预先放好点，用到时再移过来即可。注意由于两维坐标的不对称性，实现时需要注意增加行和增加列的先后顺序。

这样的操作不一定能恰好契合 $n,m$ 的大小，我们截取按照这种构造方法生成的前 $n$ 个点，再将前 $n-m$ 个点在所有操作开始前就摆在它最后应在的位置上。

最后总的操作步数大约为 $\sum_{i=n-m+1}^{n}\sqrt{i}$，遗憾的是未能贴紧理论上限。

题外话

本题是来自于 UOJ #309，那道题需要维护每个点的偏好维度。当时一些提交代码是用 vector 存储每行每列上的关键点。按照前面分析这只有根号个，但是众所周知 vector 的动态操作常数很大，所以我当时就想卡下 vector 动态操作的常数。但最后 vector 莫名其妙跑得飞块，我怀疑是因为构造涉及到的点的坐标本质上只有 $O(\sqrt{n})$ 个，然后缓存非常友好。当时尝试 hack 是失败了，不过也有了现在这道题。

不下发 OJ 上的 $O(m\sqrt{n})$ checker 是因为 checker 的实现可能会对选手做题产生提示作用。

挑战最大团

from JohnVictor

算法一

我会堆暴力！期望得分 $40$ 分。

算法二

首先注意到一个性质，就是优美的图和它的补图不能同时连通。

证明：对 $n$ 归纳，设这张图为 $G$，顶点集为 $V$。

如果 $n-1$ 时成立，注意到优美的图的子图和补图仍然是优美的，我们反证，假设原图和补图都连通。

任意找出一个节点 $v$，如果它和所有的其余节点都连边，那么补图不连通，因此我们不妨假设 $v$ 在原图和补图中都有边。

我们考虑 $V- v$ 的原图 $G_1$ 和补图 $G_2$，由归纳假设它们不同时连通。

不妨假设 $G_1$ 不连通，否则我们考虑 $G$ 的补图也是一样的。假设 $G_1$ 的连通分支为 $X_1,X_2,\cdots,x_t(t \ge 2)$，由于 $v$ 不向所有点连边，所以一定存在一个连通分支，不妨设其为 $X_1$，使得 $v$ 不向 $X_1$ 中的所有点连边。

记 $S$ 为 $X_1$ 中和 $v$ 连边的点构成的集合，$T$ 为与 $v$ 不连边的点构成的集合，$X_1$ 的连通性表明存在 $a \in S,b \in T$ 使得 $a,b$ 连边。再由原图的连通性存在 $w \in X_2$ 使得 $v,w$ 连边，此时 $b-a-t-v$ 构成诱导 $P_4$，矛盾。

那么我们可以考虑递归求解这个问题，考虑答案的生成函数，如果原图不连通那么 GF 就是连通分支的 GF 相加，如果补图不连通那么一个顶点集构成团当且仅当它在补图的每一个连通分支中都构成团，也就代表这个 GF 是连通分支的 GF 相乘。

暴力 BFS 判断连通性，时间复杂度 $O(n^3)$，期望得分 $60$。

算法三

使用 std::bitset 优化上述暴力 BFS 即可，因为这个图如果连通那么补图不连通，也就是直径为 $2$，可以扩展出第一层节点之后使用或操作。时间复杂度 $O(n^3/w)$，常数很小，期望得分 $70$。

算法四

我们考虑更快的找出连通块。使用启发式分裂的思想，我们希望如果一次 BFS 将图分为大小为 $x,y$ 的两个部分，使用的代价为 $O(xy)$。

仍然应用直径为 $2$ 的性质，首先在原图和补图中各取一个度数最小的节点，然后扩展第一层节点，之后再进行并行 BFS，也就是原图和补图依次扩展一个节点，直到确认其中一个连通为止（显然原图和补图至少有一个连通），可以证明复杂度是 $O(n^2)$，期望得分 $100$。

补充一句，复杂度满足要求是因为设最小度为 $x$，那么较小的一部分大小至少为 $x+1$，而扩展的代价至多为 $x(x+y) \le 2xy$。

算法五

from djq_cpp

注意到上述算法的本质是用一棵树来刻画这个图，具体地，一个这样的图能和一棵 $n$ 个叶子的树一一对应，两个节点连边当且仅当 LCA 为奇数。

现在我们考虑建树，只用 $O(n)$ 在前 $n-1$ 个点的树中插入一个节点即可。

可以证明在插入一个节点之后，这棵树只有一条链上的节点会发生变化，因为如果互不包含的两个子树中都有向新节点连边的，容易找到一条 $P_4$，补图也一样。

现在我们只用找出这条链，具体做法是 DFS 并维护出哪些点的子树到这个新节点连边情况完全相同（全连边或者全不连边），找出不同的这一条链之后，再专门去改变这条链的节点即可，具体可以见这份代码。

时间复杂度 $O(n^2)$，常数略大于算法四，期望得分 $100$。

你将如闪电般归来

from deadecho

经 EntropyIncreaser 氏加强！！！

为了叙述方便，接下来叙述的 $k$ 是原题面中输入的 $k$ 减去 $1$。

算法一

考虑按照题意自底向上进行 DP。设 $f_{k,n}$ 是 $k$ 层，$n$ 个节点对应的答案。那么有 $f_{0,n}=[n=1]$ 和递推式 $$ f_{k,n} = \sum_{m=0}^{n-1} \binom{n-1}{m}f_{k-1,m} [n-1-m \equiv 0 \pmod 2] $$ 时间复杂度 $\Theta(kn^2)$，期望得分 $15\sim 25$。

算法二

算法一中的递推式可以写作卷积，因此可以用 FFT 优化，时间复杂度 $\Theta(kn\log n)$，期望得分 $25$。

算法三

考虑将问题写作生成函数，设 $F_k(x) = \sum_{n} f_{k,n}\frac{x^n}{n!}$，发现有关系 $$ \newcommand{\me}{\mathrm{e}} \newcommand{\d}{\,\mathrm{d}} \begin{aligned} F_0(x) &= x\\ F_k(x) &= \int_0^x F_{k-1}(u) \frac{\me^u + \me^{-u}}2 \d u \end{aligned} $$ 我们发现直接积分是没有显式表达式的，但考虑建立辅助生成函数 $F_k(x) = G_k(\frac{\me^u -\me ^{-u}}2)$。

接下来我们记 $\cosh x=\frac{\me^x+ \me^{-x}}2,\sinh x = \frac{\me^x -\me^{-x}}{2}$。但我们接下来不会用到任何双曲三角函数结论。 $$ \begin{aligned} F_k(x) &= \int_0^x G_{k-1}(\sinh u) \cosh u \d u\\ &= \int_0^x G_{k-1}(\sinh u) \d (\sinh u)\\ &= \int_0^{\sinh x}G_{k-1}(t) \d t\\ G_k(x) &= \int_0^x G_{k-1}(t)\d t \end{aligned} $$ 而我们的目的就是算出 $[x^n] F_k(x)$，因此我们可以分为计算 $G_k(x)$ 的前 $n$ 项系数和所有的 $[x^n] (\sinh x)^m, m\le n$。

由 $G_0(\frac{\me^x -\me^{-x}}2)=x$，根据复合逆关系，设 $u=G_0$，那么 $\frac{\me^u-\me^{-u}}2=x$，设 $t=\me^u$，也就有 $\frac {t-1/t}2=x$，解得 $t=x+\sqrt{1+x^2}$，也就有 $G_0(x) = \sinh^{-1}x = \ln(x+\sqrt{1+x^2})$。

$G_k(x)$ 是将 $G_0(x)$ 连续积分 $k$ 次，也就有 $[x^n]G_k(x) = \frac 1{n^{\underline k}}[x^{n-k}]G_0(x)$，预处理阶乘就可以做到 $\Theta(n)$ 计算 $G_k(x)$ 的系数。

而根据 Lagrange 反演公式，有 $[x^n](\sinh x)^m = \frac m n [x^{n-m}]\left( \frac{x}{\sinh^{-1}x} \right)^n$。

综上，我们可以通过计算生成函数的幂在 $\Theta(n\log n) \sim \Theta(n\log^2 n)$ 内完成。预计得分 $40$。

算法四

在 $n$ 很大的时候，我们不得不考虑 $F_k$ 的具体形式。

我们考虑二元 GF $\mathcal F(x,t) = \sum_k F_k(x)t^k$，可依 $F_k$ 的递推关系列出方程 $$ \begin{aligned} \mathcal F(x,t) &= x + t\int_0^x \mathcal F(u,t) \cosh u \d u\\ \frac{\partial}{\partial x}\mathcal F &= 1 + t\mathcal F \cdot \cosh x \end{aligned} $$ 根据一阶 ODE 的通解形式，确定常数项之后我们得到了 $$ \mathcal F(x,t) = \me^{t\sinh x} \int_0^x \me^{-t\sinh u} \d u $$ 提取 $[t^k]$，可知 $$ F_k(x) =\sum_{j=0}^k \frac{(\sinh x)^{k-j}}{(k-j)!} \cdot \int_0^x \frac{(-\sinh u)^j}{j!} \d u \tag{1} $$ 注意到有积分 $$ \int_0^x \me^{ju} \d u = \begin{cases} \frac{\me^{jx} - 1}{j} & j\neq 0\\ x & j=0 \end{cases} $$ 可知 $F_k$ 的形式为 $x^a \me ^{cx}$ 的线性组合，其中 $0\le a\le 1, -k\le c\le k$。

可以使用上述和式，通过 FFT 在 $\Theta(k^2\log k)$ 时间内计算出 $x^a\me ^{cx}$ 基下的系数，如果暴力按照积分式递推系数则可做到 $\Theta(k^2)$。预计得分 $60$，和算法三拼起来可以获得 $75$。

算法五

我们希望加速 $x^a \me^{cx}$ 基的系数的计算，考虑 $F_k(\ln x) = G_k(\frac{x-1/x}2)$ 是一组 $x^c(\ln x)^a$ 基，为了借助微分方程的力量，我们首先考虑 $G_k(x)$ 的微分性质。

设 $A(x) = \left(\sinh^{-1} x\right)' = (1+x^2)^{-1/2}$，记其系数为 $a_n$。那么有递推式 $$ na_n = (1-n)a_{n-2} $$ 设 $b_n = \frac{a_{n-k-1}}{n^{\underline {k+1}}}$，即对应的 $B(x)=G_k(x)$ 为 $A(x)$ 做 $k+1$ 次积分，可得递推式 $$ \begin{aligned} (n-k-1) a_{n-k-1} &= (2-n+k) a_{n-k-3}\\ (n-k-1) b_n \cdot n^\underline{k+1} &= (2-n+k) b_{n-2} \cdot (n-2)^{\underline {k+1}}\\ n(n-1)(n-k-1)b_n &= -(n-k-1)(n-k-2)^2b_{n-2}\\ (n-k-1)(n(n-1)b_n + (n-k-2)^2b_{n-2}) &= 0\\ n(n-1)b_n + (n-k-2)^2b_{n-2} &= \frac 1{(k-1)!} \cdot [n=k+1]\\ k^2 x^2B(x) + (1-2k)x^3B'(x) + x^2(1+x^2)B''(x) &= \frac {x^{k+1}}{(k-1)!}\\ k^2 B(x) + (1-2k)xB'(x) + (1+x^2)B''(x) &= \frac {x^{k-1}}{(k-1)!} \end{aligned} $$ 我们考虑设 $X=\frac {x-1/x}2$，令 $P(x)=B\left( \frac{x-1/x}2 \right)$，考虑列出 $P,B$ 之间的导数关系。 $$ \begin{aligned} P'(x) &= \left( \frac{1+x^{-2}}2 \right) B'(X)\\ P''(x) &= \left(\frac {1+x^{-2}}2\right)^2 B''(X) - x^{-3} B'(X)\\ \Rightarrow B'(X) &= \left( \frac{2}{1+x^{-2}} \right) P'(x)\\ B''(X) &= \left( \frac{2}{1+x^{-2}} \right)^2 P''(x) + x^{-3} \left( \frac{2}{1+x^{-2}} \right)^3 P'(x) \end{aligned} $$ 这就导出了 $P(x)$ 满足的方程 $$ \begin{aligned} k^2B(X) + (1-2k)X B'(X) + (1+X^2)B''(X) &= \frac{X^{k-1}}{(k-1)!}\\ k^2 P(x) + (1-2k)X \cdot \left( \frac{2}{1+x^{-2}} \right) P'(x) + (1+X^2) \cdot \left[\left( \frac{2}{1+x^{-2}} \right)^2 P''(x) + x^{-3} \left( \frac{2}{1+x^{-2}} \right)^3 P'(x)\right] &= \frac{X^{k-1}}{(k-1)!}\\ k^2 \left( \frac{1+x^{-2}}2 \right)^3 P(x) + (1-2k)X \cdot \left( \frac{1+x^{-2}}2 \right)^2 P'(x) + (1+X^2) \cdot \left[\left( \frac{1+x^{-2}}2 \right) P''(x) + x^{-3} P'(x)\right] &= \frac{X^{k-1}}{(k-1)!} \cdot \left(\frac{1+x^{-2}}2\right)^3\\ k^2 (1+x^2) P(x) + ((1+2k)x + (1-2k)x^3) P'(x) + ( x^2+x^4) P''(x) &= \frac{X^{k-1}}{(k-1)!} \cdot (1+x^2) \end{aligned} $$ 由此我们已经得到了 $P(x)$ 满足的一个微分方程，将其提取 $[x^n \ln x]$ 设为 $g_n$，提取等式两边的 $[x^n\ln x]$ 可得递推式 $$ (n+k)^2g_n + (n-2-k)^2g_{n-2} = 0 $$ 再提取 $[x^n]$ 设为 $f_n$，提取等式两边的 $[x^n]$ 可得递推式 $$ (n+k)^2 f_n + (n-2-k)^2 f_{n-2} + 2(n+k)g_n + 2(n-k-2)g_{n-2} = [x^n] \frac{X^{k-1}}{(k-1)!} (1+x^2) $$

还需解决边界值问题，根据 $(1)$ 式可知： $$ \begin{aligned} f_k &= \frac 1{2^k}\sum_{j=1}^k \frac{(-1)^j}{(k-j)!j!\cdot j} = \frac {-1}{2^k k!} H_k\\ g_k & = \frac 1{2^kk!} \end{aligned} $$ 由此即可从大到小递推，在 $\Theta(k)$ 时间内计算出系数，然后通过线性筛，只需计算 $\pi(k) \sim \frac k{\ln k}$ 次快速幂，时间复杂度 $\Theta(k\log_k \min(n, p))$。预计得分 $100$。

后记

在操作过程中，我们考虑了复合 $B\left( \frac{x-1/x}2 \right)$，但 $B$ 是形式幂级数，复合的 $\frac{x-1/x}2$ 既有正次项又有负次项，其即使拓展到 Laurent 级数也无法定义复合，但我们对微分方程的推导得到的，对于 $x^c(\ln x)^a$ 组成的「生成函数」给出的系数递推式也确实给出了正确的答案。如何更加严格刻画这种推导，或许是个有趣的问题。