2023-07-05

UOJ Round #10

A. 汉诺塔

$n \le 500$

假设最后所有圆盘都在第三根柱子上。

那么把第一根柱子上的圆盘依次放到第二根柱子上，碰到编号为 $n$ 的圆盘就拿出来放到第三根柱子上。

然后把第二根柱子上的圆盘依次放到第一根柱子上，碰到编号为 $n - 1$ 的圆盘就拿出来放到第三根柱子上。

$\cdots$

如此循环往复。

时间复杂度 $\mathcal O(n^2)$。

$n \le 10000$

$\mathcal O(n^2)$的算法没有前途，考虑分治。

假设第一根柱子上有编号为 $[l, r]$ 的乱序的元素，把这根柱子上的圆盘依次取出，编号不超过 $mid = \frac{l + r}{2}$ 的圆盘放到第二根柱子上，其它的圆盘放在第三根柱子上。

然后对第二根和第三根柱子上新加入的若干个圆盘进行逆序排序，可以发现这是一个以另外两根柱子为第一根柱子的规模更小的子问题，可以递归解决。

假设要按照从顶到底递增的顺序排列，先把第二根柱子上的圆盘依次移动回第一根柱子，再把第三根柱子上的圆盘移回来，否则就先移回第三根柱子上的圆盘。

时间复杂度 $\mathcal O(n \log n)$。

$n \le 5$

发扬人类智慧发现 $n = 4$ 时第一次 $1 - 2$ 第二次 $2 - 3$，四个点就区别开了。

$n = 5$ 时连边 $1 - 2, 3 - 4$ 和 $2 - 3, 4 - 5$，首先判断出 $1, 5$，然后顺着推出 $2, 3, 4$。

$n \le 1000$

可以拓展到 $n$ 更大的情况，连成一条链，先判断出最边上的点，然后顺着往里推推出剩下的点。

时间复杂度 $\mathcal O(n^2)$。

$m \le 4$
$n \le 5$

暴力枚举指令集合，判断是否合法。

时间复杂度 $\mathcal O(T n!^m)$。

$m \le 30$
$n \le 1000$
$B_{i, j} \equiv i + j - 1 \pmod m$

可以发现一个完善的指令系统一定是一个群。

给出的群 $G$ 是一个循环群，即这个群是由某个置换 $P$ 的幂次形成的。

因为 $

=m$，所以置换 $P$ 的阶数是 $m$，可以发现阶数为 $m$ 的置换和群 $G$ 是一一对应的，那么问题就转化为了求阶数为 $m$ 的置换的个数。

假设一个置换的循环个数为 $k$，每一个置换的长度为 $A_i$，那么显然这个置换的阶数是 $\text{lcm} \{ A_i \}$，可以用 DP 来求解阶数为 $m$ 的循环个数。

设 $f[i][j]$ 表示长度为 $i$，阶为 $j$ 的置换的个数。

枚举编号最大的元素所对应的循环大小 $k$，这个循环的形态一共有 $(k - 1)!$ 种，而这个循环内除了编号最大元素以外的元素的选取方法有 $\binom{i - 1}{k - 1}$ 种，因此可以得到递推式：

$f[i][j] = [\text{lcm}(a, k) = j] \times f[i - k][a] \times \binom{i - 1}{k - 1} \times (k - 1)!$

时间复杂度 $\mathcal O(nm^3)$。