这里是第一次造UR的JRY。

因为我根本不会抽代，所以把第三题题解写成了民科状物体，请大家轻喷..

我已经累的说不出其他感想了..等清华集训结束以后一起写在我的博客上吧..

[upd]A题 $O(n \sqrt n)$ 做法现已加入豪华午餐。

汉诺塔

By vfleaking

题解 By C_SUNSHINE

算法1

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

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

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

……

如此循环往复就可以了。

操作数复杂度$O(n^2)$，时间复杂度$O(n^2)$，可以得到$60$分。

算法2

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

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

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

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

操作数复杂度$O(nlogn)$，时间复杂度$O(nlogn)$，可以得到$100$分。

算法3

应广大群众的要求，我来补上 $O(n \sqrt n)$ 的做法的题解啦。

因为我自己也没有写过，所以具体的实现方法我也不知道啦...大致的思路就是每一次，我们从汉诺塔中把最小的 $\sqrt n$ 个数给移到最顶上，然后把它们排序，最后把这些数塞到最底下不考虑。这样的操作次数是 $O(n \sqrt n)$ 的，但是这种实现方式的常数可能偏大，可能需要卡卡常数才能过。

世界线

By xllend3

算法一

经过人类智慧，可以发现 $n=4$ 时只需要第一次 $1-2$ 第二次 $2-3$，那么四个点就都区别开了。

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

可以通过 1,2 两个点获得 20 分。

算法二

观察一下 $n=4$ 和 $n=5$ 的解，发现这种解可以拓展到 $n$ 更大的情况。即连成一条链，先判断出最边上的点，然后顺着往里推推出剩下的点。

由于一个点只会和另外的一个点连边，所以期望要询问 $O(n)$ 次，那么询问次数为 $O(n^2)$。

可以通过 1,2,3,4 获得 40 分。

算法三

如果想减少询问次数，其实就是减小块数。因为询问的复杂度是块数乘 $n$ 的（只需要对于每个块扫一遍所有的点即可）。

由于两次块数之积不能小于 $n$ （否则两个点两次都在同一块怎么看出来是谁呢），所以块大小之和最小只能到根号范围。

那么重点就在于怎么鉴定哪些块是哪些块。使用块大小来鉴别是一个不错的办法。

对于第5个点和第7个点，注意到 $n$ 满足 $n=\frac{k \times (k+1)}{2}$，那么将所有的数排列在 $k \times k$ 的网格图（点 $(i,j)$ 在网格图中当且仅当($1\leq i,j\leq n)$）中满足 $i\leq j$ 的位置，第一次将 $x$ 相同的归为一组，第二次将 $y$ 相同的归为一组。那么通过每个点每次所在的块的大小就可以轻松判断出这个点是谁。

结合前面可以通过1,2,3,4,5,7获得60分。

算法四

假如 $n$ 不能表示成 $\frac{k \times (k+1)}{2}$，那么块大小分法就无效了，因为怎么分都会有两个块大小相等。这时候就要想别的办法了。

还是按照上面的方法排列这些点，多出来的部分排在 $k+1$ 行的前几个位置。那么纵向的块大小已经两两不同了，只有横向有两个块相同，那么只需要区分它们就行了。

那么将最后一行的最后一个点拿出来，移到 $(k+1,k+1)$，询问的时候首先找出这个点的位置就可以区分这两个块了。

由于纵向只有 $(k+1,k+1)$ 和 $(k,k)$ 两个两个点，所以直接根据这两个块的大小区分即可。

注意到这样做在 $n=\frac{k \times (k+1)}{2}-1$ 时会由于横向最后两个块大小相同而无法区分，所以过不了后三个点。

结合前面可以通过1,2,3,4,5,6,7获得70分。如果懒得特判前两个点就只有60分了。

算法五

既然 $n=\frac{k \times (k+1)}{2}-1$ 会挂那就不拿最后一个点，随便拿一个其他的，那它不就成了唯一一个大小为1的了吗？于是就可以愉快地解决 $n=\frac{k \times (k+1)}{2}-1$ 的情况。

但是等一等让我们算算询问次数：$n\sqrt{2n}=2800000$。所以还是过不了后三个点T_T

算法六

接下来就是精彩的卡常时间！

由于每次询问之后已经被归到某一块的点显然是可以不用再次询问的，于是把已经归类的都删掉，你就获得了一个 $0.4$ 的常数！

为啥常数这么奇怪呢？因为随机排列后期望选到的是更大的块，所以大块会更有可能被优先删掉。于是就小于 $0.5$ 辣！

可以通过所有测试点！（手动鼓掌熊）

算法七

那么还能继续优化吗？

假如刚开始就能知道这个块大不大那不就可以不用拼脸了吗？也就是说需要优先判断可能最终比较大的块。

那么考虑换一种询问方法：不枚举块，而是枚举每个元素，尝试将它归入现在存在的块中，假如归不进那么就新开一块。

假如尝试的顺序就是块出现的顺序的话容易发现两种做法的询问次数是一样的。但是我们可以不按它出现的顺序来！可以按照当前块大小从大到小询问！

这种做法大概可以优化掉10%左右的询问次数。这样就不怕其他人凭借欧洲人的优势抢走抱枕辣！

算法八

由于每个询问成功地概率基本都是小于 $0.5$ 的，所以每次挑选成功概率最大的询问就可以获得最多的信息量。 假如一个点已经被得知不和某些点连通，那么它跟其他点连通的概率就会大不少，也就是说不停地询问一个点直到确定他的位置已经是一种非常不错的选择了，也就是说改变这里的优化余地并不是很大。 那么接下来的问题就是判断属于哪个块的概率更大。注意到假如有一个块是 $k-2$ 一个块是 $k-1$，那么属于 $k-2$ 的概率显然要高于 $k-1$ 的概率，也就是说直接从大到小询问并不是最优的策略，可能从中间开始询问更优。那么就需要算出每个块的期望大小，根据期望大小和实际大小的差来确定询问先后。

由于每个块的期望大小并不能那么快地算出来，所以就需要使用比较精确的估价函数来估价（然而这样看起来还是有点困难）。不过应该可以打表？

于是我也不知道怎么继续优化了。欢迎使用更厉害的算法艹算法七。

列队

By sevenkplus

题解 By jiry_2

算法一

我们暴力枚举所有可能的指令集合，然后判断一下它是不是符合 picks 博士的构思即可，时间复杂度大约是 $O(Tn!^m)$，加一些剪枝就能拿到20分了。

算法二

相信大家都能看出这是一个和群有关的问题，可以发现一个完善的指令系统一定是一个群。观察第三个点和第四个点的部分分，可以发现这个时候给出的群 $G$ 是一个循环群，即这个群是由某个置换 $P$ 的幂次形成的。

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

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

令 $dp[i][j]$ 为长度为 $i$，阶为 $j$ 的置换的个数。转移的时候，我们可以枚举编号最大的元素所对应的循环大小 $k$，这个循环的形态一共有 $(k-1)!$ 种，而这个循环内除了编号最大元素以外的元素的选取方法有 $\binom{i-1}{k-1}$ 种，因此就可以得到递推式：

暴力转移一波，时间复杂度是 $O(nm^3)$ 的，结合一下算法一就能得到 $40$ 分了。

算法三

这题给定了一个群 $G$，实际上是要求 $G$ 到 $S_n$ 的单同态的个数。

考虑同态 $f: G \rightarrow S_n$，令 $K=\text{ker} \ f$，那么我们要统计的就是 $K=\{1\}$ 的同态 $f$ 的个数。因为有 $G/K$ 同构于 $\text{im} \ f$，所以满足 $\text{ker}\ f=K$的同态 $f$ 的个数等于 $G/K$ 到 $S_n$ 的单同态个数。

因此我们可以枚举 $G$ 的所有阶大于1的正规子群 $H$，那么 $G$ 到 $S_n$ 的单同态个数就等于 $G$ 到 $S_n$ 的同态个数减去 $G/H$ 到 $S_n$的单同态个数。那么如果我们能求出 $G$ 到 $S_n$ 的同态 $f$ 的个数，就能递归到规模为 $|G|/|H|$ 的子问题了。

到这儿问题就转化成了给定一个群 $G$，求 $G$ 到 $S_n$ 的同态的个数。

令 $H$ 是 $G$ 的一个指数为 $K$ 的子群，那么 $G/H$ 中含有 $K$ 个元素。用 $1$ 到 $K$ 给这 $K$ 个元素编号，固定 $H$ 的编号是 $1$，那么显然有 $(K-1)!$ 种编号方式。同时，可以发现仅存在一个 $G$ 在 $G/H$ 上的作用，我们把这个作用中 $G/H$ 中的元素都用它的编号来代替，那么就可以得到一个 $G$ 到 $S_K$ 的同态，因此，通过这种方式，一个指数为 $K$ 的子群 $H$ 就给出了 $(K-1)!$ 个 $G$ 到 $S_K$ 的同态。

考虑这样的同态满足怎么样的特性，可以发现这样同态 $\phi$ 满足，所有固定了排列中的 $1$ 的元素恰好组成了 $H$ 且 $\text{\phi}$ 在 $1$ 到 $n$ 上是可迁的。我们令这样的同态的个数为 $t_K$，阶为 $K$ 的子群个数为 $a_K$，根据上一段的分析可以得到 $a_K=\frac{t_K}{(K-1)!}$。

现在考虑 $G$ 到 $S_n$ 的同态 $f$，我们枚举这个同态中 $1$ 的轨迹的大小 $K$，那么轨迹集合就有 $\binom{n-1}{K-1}$ 种，而 $G$ 在轨迹集合上的作用有 $t_K$ 种（因为这一部分一定是可迁的），把 $1$ 的轨迹去掉之后就得到了一个 $n-K$ 规模的子问题，因此我们就得到了一个递推式（令 $h_K$ 为 $G$ 到 $S_n$ 的同态的个数）：

把 $t_k$ 用 $a_k$ 带入即可得到一个能算的递推式啦..具体实现的时候就直接按照定义搜搜搜算算算就行啦..$m \leq 30$ 的数据范围无论是子群还是正规子群的个数都不多，直接暴力递归子问题什么的就好了。