新年的破栈

from wyx528

算法一

容易发现，每次可能的操作不会超过 3 种，因此只要在需要决策的时候暴力枚举其中的一种即可，指数级复杂度，可以得到 20 分。

算法二

由于要求字典序最小，所以必然要把尽可能小的数提前出栈，更特殊地，一定会把最小的数最先出栈。

当最小的元素出栈时，记栈底元素为 $x$，栈顶元素为 $y$，未进栈的元素中最小值为 $z$，则下一个要出栈的元素必为 $min\{x,y,z\}$。由于题目保证给定的元素互不相等，所以这一步是没有歧义的，也就是说 $x,y,z$ 中任意两个都不会相等。这样，我们便得到了输出序列的第二个数。

可以发现，只要重复这个贪心过程即可取得最优解。使用朴素算法，选取未进栈元素最小值的时间复杂度为 $O(n)$，因此完成一组数据的时间复杂度为 $O(n^2)$，可以得到 60 分。

算法三

使用堆或者平衡树来优化算法二中选取未进栈元素最小值的时间复杂度，使之降为 $O(\log n)$，这样完成一组数据的时间复杂度变为 $O(n\log n)$，可以得到 100 分。（比赛时还真有人这么干……）

算法四

实际上，我们可以发现，每次选取未进栈元素最小值时，所涉及的决策范围必然是 $A[i\dots n]$，也就是序列 $A$ 的一段后缀。进一步的，随着入栈操作的进行，这个可能的决策后缀也会变得越来越短，因此只需要维护序列 $A$ 后缀的最小值，及最小值所在的位置，便可以将选取未进栈元素最小值的时间复杂度降为均摊 $O(1)$，这样完成一组数据的时间复杂度变为 $O(n)$，也可以得到 100 分。

新年的网警

from sevenkplus

题解 from jiry_2

算法一

可以发现每一个人第一次听到谣言的时间实际上就是发起人到达这个人的最短路径长度（假设边权都是 $1$），不妨假设最后一个听到谣言的人在时刻 $t$ 的时候听到了谣言，那么除了谣言发起人以外，其他人回答网警的数值都应该在 $t-n$ 到 $t$ 之间。为了隐藏自己，谣言发起人回答的数也一定在这个区间之内。

我们不放假设 $t$ 等于一个确定的数（比如 ${10}^9$），那么网警听到的口供最多只有 $n^2$ 种（取决于谣言发起人是谁以及谣言发起人回答的时间）。如果存在两对数对 $(a,b)$ 和 $(c,d)$ 满足 $a\ne c$ 且当谣言发起人是 $a$，他回答的时间是 $b$ 时网警得到的口供和谣言发起人是 $c$，他回答的时间是 $d$ 时网警得到的口供是完全相同的，那么 $a$ 和 $c$ 都是安全的谣言发起人。

于是我们可以把这 $n^2$ 种情况的口供的模拟出来，然后排一个序判判断一下一份口供是否和其它的口供相等。

时间复杂度 $O(T{n}^3\log n)$，期望得分 $30$ 分。

算法二

我们可以发现，一个谣言发起人 $i$ 是安全的，当且仅当他至少满足下列条件中的一个：

1. 他是大老师（在群里面只认识一个人）。
2. 他认识大老师 （即认识一个满足条件 1 的人）。
3. 存在一个人 $j$ 使得 $i$ 和 $j$ 认识的人是完全相同的（这时忽略 $i$ 和 $j$ 的认识关系）。

首先这三个条件的充分性显然，考虑证明它的必要性。

假设存在两个人 $i$ 和 $j$，他们都不满足条件 1 和条件 2，他们认识的人不完全相同且存在一种可能性使得网警无法分辨 $i$ 和 $j$。那么我们分两种情况考虑：

1. 他们至少有一个共同认识的人 $k$，那么为了让 $k$ 听到谣言的时间一样，$i$ 和 $j$ 发起谣言的时间必定相同，假设这个时间是 $t$。同时由假设，存在一个人 $p$，他恰好被两个人中的一个人认识，此时 $p$ 两次听到谣言的时间必定不相同（一次是 $t+1$，一次必定大于 $t+1$），矛盾。
2. 他们没有共同认识的人。那么假设 $i$ 是在 $t1$ 时刻散布的谣言， $j$ 是在 $t2$ 时刻散布的谣言。考虑 $i$ 到 $j$ 的一条最短路，那么这条最短路的长度必定大于 $2$（我们假设长度是 $d$）。考虑最短路上离 $i$ 最近的点是 $p$，离 $j$ 最近的点是 $q$，为了让 $p,q$ 两次听到谣言的时间相同，那么就有 $t1+1=t2+d-1$ 和 $t2+1=t1+d-1$。这个方程一定是无解的（因为 $d>2$），矛盾。

于是这个结论就得到了证明。因为条件 1 和 2 都很好判断，所以接下来只考虑条件 3。

我们可以枚举每一对人 $(a,b)$，然后忽略掉 $a$ 和 $b$ 之间的认识关系，然后判断它们认识的人是否相同。当然直接暴力判断的时间复杂度是 $O(nm)$ 的，我们可以用压位或者哈希来加速一下。这样时间复杂度就变成了 $O(T{n}^2)$ 或者 $O(\frac{T{n}^3}{32})$ 啦。

期望得分 $60$ 分。

算法三

算法二的瓶颈在于枚举每一对人，而实际上需要忽略 $a$ 和 $b$ 之间认识关系的情况只有 $m$ 对，对于其他情况，我们只需要把一个人所有相邻的点都拿出来哈希一下，然后和算法一一样排序一下判断是否和其他人相同就行啦。

这样时间复杂度就变成了 $O(Tn\log n+Tm)$。

比赛的时候好像有人作死把哈希的模设成了 ${10}^9$ 级别然后被卡成 $60$ 分了？这个时候只需要搬出企鹅 QQ 这道题然后露出一个意味深长的微笑就好啦。

新年的繁荣

from Rating_Jia_Su_Qi

算法一

对于 subtask1，直接把完全图建出来跑 kruskal 算法就好啦。

时间复杂度 $O(n^2\log n)$，期望得分 $15$ 分。

算法二

对于 subtask2，依然把完全图建出来，但是我们可以跑 prim 算法。

有人说我只会 kruskal 怎么办！可以发现 kruskal 算法的瓶颈在于排序，注意到边长不会超过 $2^m$，于是可以用桶排来降低复杂度。

时间复杂度 $O(n^2)$ 或 $O(n^2\alpha (n))$，期望得分 $30$ 分。

算法三

对于 subtask3，点权只有两种 $0$ 或 $1$，只有两个 $1$ 相连的时候才会有 $1$ 的贡献，那么把所有的 $1$ 全部连起来就好啦，答案就是 $1$ 的个数 $-1$。

时间复杂度 $O(n)$，结合算法二期望得分 $40$ 分。

算法四

对于 subtask4，考虑 kruskal 算法，我们可以发现如果选了某个点连出去的最大边肯定是可行的，由于 $a\mathrm{and}b\le a$，所以对于相同权值的点我们可以先连好，这样最多只剩下 $2^m$ 个点了，再使用算法二就可以通过这些部分分。

时间复杂度 $O(4^m)$，结合算法二期望得分 $55$ 分。

算法五

对于 subtask5，顺着刚才的思路，如果 $a\mathrm{and}b=a$，那么肯定可以将 $a$ 和 $b$ 连起来，那么连到 $a$ 上肯定都没有连到 $b$ 上去优，就可以把 $a$ 删去了。最后留下的所有的点都互不包含，这样的点数最多是 $(\genfrac{}{}{0ex}{}{m}{m/2})$ 的，那么在这些点上跑算法二就可以了。

时间复杂度$O\left({(\genfrac{}{}{0ex}{}{m}{m/2})}^2\right)$，结合算法二期望得分 $70$ 分。

算法六

来考虑一下普通的最大生成树除了 kruskal 和 prim 还有什么算法，既然选择最大边是对的，那么我们可以对于每个点选择最大边连好，缩完联通块，然后再对于每个联通块选择最大边继续缩！缩了 $i$ 次以后每个联通块大小都至少是 $2^i$，所以只要缩 $\log n$ 次就行了（这个东西居然有名字，叫 Boruvka 算法）。

那么现在的问题就是这样，有 $n$ 个数，每个数有一个颜色，对于每个数 $a$ 求出一个异色的数 $b$，使得$a\mathrm{and}b$最大。这里我们可以使用 trie 或者子集和变换。

如果把 $\mathrm{and}$ 改成 $\mathrm{xor}$ 我想大家都会用 trie 来做，先把每个数插入 trie 中，维护每个点的子树中颜色的最大值和最小值，这样就能知道是否有除了当前查询的颜色以外的其他颜色了，询问就直接跑一跑就好了。但是这里是 $\mathrm{and}$，如果当前询问的数是 $0$，那么两个子树都需要跑，这样的复杂度是不对的，但我们发现永远不会只需要跑 $0$ 子树，而不跑 $1$ 子树，那么我们就可以先建出 trie，然后从下到上依次将 $1$ 子树合并到 $0$ 子树上去，这样每个点的左子树就变成了 $0+1$，右子树还是 $1$，询问到 $0$ 就到左子树，到 $1$ 就跑右子树，就变成 $O(m)$ 了。而建树的时候可以发现每个点被它的每个祖先都要访问一次，这样的复杂度是 $O(m{2}^m)$ 的。

可以发现之前的合并以后每个点代表着它的子集，于是可以把 trie 改成子集和变换，关于子集和变换可以看吕凯风学长的2015年国家集训队论文《集合幂级数的性质与应用及其快速算法》。复杂度和 trie 相同。

时间复杂度 $O((n+2^m)\cdot m\log n)$，期望得分 $100$ 分。

算法七

这个算法赛前并没有出题人/验题人/出题火车想到，但在考场上 BillXu2000 首先想到了这个算法，遗憾的是，他开小了数组所以没能A掉，另外一位参赛选手 Yemengmeng 也想到并使用这个算法A掉了本题。

首先我们使用算法四的思想去重，接着我们从大往小枚举边权 $p$ ，并用一个数组$a_p$来存储一个满足 $w\mathrm{and}p=p$的一个点权 $w$ （没有就置为空），对于每个 $p$ ，我们用类似子集和的方式枚举所有 $q=p\mathrm{or}{2}^i(0\le i<m)$，并把这些$a_q$组成的集合 $S$ 求出来，由于 $p$ 是从大到小枚举的，显然把 $S$ 涉及的各个联通块用权值为 $p$ 的边连起来一定最优。这样我们就把 $a_q$ 组成的集合合并到了一个联通块内，我们再从 $S$ 中任意取出一个元素放入 $a_p$ 作为这个联通块的代表即可，由于 $p$ 从大到小枚举，每一步计算中需要用到的所有信息都已经在之前计算好了。

求每个点所在联通块以及合并这些联通块可以使用并查集维护，这样算法复杂度就是 $O(m{2}^m\alpha (n))$ 。

具体可以去看代码：http://uoj.ac/submission/48502

算法八

最大生成树算法就是个垃圾！我们抛掉不要！这个算法一点都不玄学！接下来就让我们看看玄学算法。

我们依然是不断地合并联通块，不过现在是按照二进制位从高到低，对于每一个联通块我们都维护一个 trie，比如当前考虑第 $k$ 位，将所有具有 $1$ 子树的联通块都取出来分治到 $k-1$ 层，然后将这些块合并，和剩下的块一起分治到 $k-1$ 层。

这个算法比较玄学，复杂度我也不会算，实际运行起来还是很快的。

时间复杂度$O(\text{玄学})$，期望得分 $100$ 分。

具体可以去看的代码：http://uoj.ac/submission/48529

这个算法相比前面的算法优越之处在于他的时空复杂度在一定程度上不严格依赖于 $2^m$ ，所以这个算法可以跑出 $m$ 比较大的数据，本机测试 $m=30$ 的数据只需要 $1s$ 不到。如果有老司机会证明这个算法的复杂度或者能卡掉这个算法，欢迎找我们联系。

新年的腮雷

from saffah

一句话题解：二分答案+逆向思维。想看AC算法请直接跳到算法九。

算法一

写一个最裸的大暴力（枚举每次选哪$m$个，以什么顺序选），时间复杂度为$O(n{!}^2)$（于$m=2$时达到最坏情况），可以通过子任务1，获得13分。

算法二

五万两秒的范围，一看就是不必在意常数的两个log。

对于$n=m$的情况，可以认为是在$a$与$b$序列间建立一种匹配，最小化最大的匹配两数之和。

看到“最大值最小”第一个想到的当然是二分答案了。为了解决“是否能使最大的和不超过$x$”这个问题，我们可以以任意顺序依次考虑$a$中的每一个数$a_i$，将$b$中小于等于$x-a_i$的最大的数与$a_i$匹配（删掉）。如果对于某个数找不到对应的数则答案$x$不可行，否则$x$可行。

使用很多数据结构（比如multiset）都可以在$O(n\log n)$时间检验一个$x$的可行性，从而总时间复杂度为$O(n\log n\log U)$，可以通过子任务2获得11分。

算法三

上面的算法其实做麻烦了，而且“任意顺序”这个也太随意了。我们把“任意顺序”换成“从大到小的顺序”，最终可以得出：只需将$a$和$b$按照相反的方向排序（比如$a$从小到大，$b$从大到小）然后形成自然的匹配关系即可。

时间复杂度$O(n\log n)$。具体的证明与本题几乎无关，略。相信大家想一想都会证。

算法四

对于所有的$a$都相同的情况，还是考虑二分答案。设当前考虑的答案是$x$。

由于$b$可以是个十分奇怪的东西，我们考虑合并的逆过程：分割。一开始我们只有一个威力为$x$的雷，每次可以选择一个雷，设其大小为$p$，则将其分割成威力为$p-b_1,p-b_2,\cdots ,p-b_m$的$m$个雷。要求最终拥有$n$个雷时，每个雷的大小都不小于$a_1$。

策略是显然的。设$b$中最大的元素为$B$，则每次任选一个威力至少为$a_1+B$的雷，将其拆分，直到总雷数达到$n$个（$x$可行），或没有雷可以拆了（$x$不可行）。

时间复杂度$O(n\log n\log U)$，可以通过子任务3获得24分。

算法五

上面的算法其实做麻烦了，而且“任选一个”这个也太随意了。我们把“任选一个”换成“选一个最大的”。这样无论二分出的是什么答案，拆分的策略（或者说，拆分树）都是一样的。所以只需令$x=0$把这棵树建出来，则答案就是$a_1$加上树的最大深度。

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

算法六

对于$m=2,b=\{1,1\}$的数据，可以每次选择最小的两个合并。证明如下；

设$p$与$q$是最小的两个物品。如果$p$不与$q$合并，设$p$与物品$s$合并，$q$与物品$t$合并，其中$s,t$可以是原有的物品，也可以是原有物品经过若干次合成得到的物品。

如果$s$的合成路线不需要$q$，并且$t$的合成路线不需要$p$，则不如改为将$p$与$q$合并，$s$与$t$合并。

否则，不妨设$s$的合成路线需要$q$（因为$s$的合成路线需要$q$并且$t$的合成路线需要$p$是不可能的），那我们把将$q$与$t$合并改为$p$与$q$合并，得到的物品$s^{\prime }$再与$t$合并。

无论如何，总代价都不会变大，所以每次可以选择最小的两个合并。

时间复杂度$O(n\log n)$，可以通过子任务4获得6分。

但是如果你只写了子任务4的程序，可以顺便通过子任务6和7，获得15分。

算法七

威力的设定总是让人们摸不着头脑。

我们定义威力为$x$的雷的能量为${\alpha }^x$，其中对于子任务457，$\alpha =2$，而对于子任务6，$\alpha =3$。

这样定义的原因是，对于“理想的合并”情况（即所有的$x_i+b_i$都相等时），能量总和保持不变。对于非理想的情况，能量总和只能增加而不能减少。由于最后只剩下一个雷，那么它的威力至少是$\lceil {\log }_{\alpha }\sum _i{\alpha }^{a_i}\rceil$。

直接输出这个数是不对的。例如，考虑$a=\{1,1,1,1,3\},b=\{1,2,2\}$，这样计算的答案是$4$，但是答案应该是$5$。

不过在$n$很大并且$a$随机的情况下是卡不掉的。因为这样算出的答案相比${\log }_{\alpha }\sum _i{\alpha }^{a_i}$有较多的盈余。

总之这样的乱搞可以过掉子任务4567，获得24分。

算法八

把以上各种乱搞合起来可以通过前7个子任务，获得72分。

（以及我也不知道有什么奇怪的算法，所以放了一点$50$的数据）

算法九

终于开始说正解了。

还是二分答案。设当前答案为$x$，则问题转化为：是否能够进行若干次合并，使得最后的猴腮雷威力不超过$x$。

还是逆向思维。问题转化为：是否存在一种拆分方案，能够从一个$x$的猴腮雷开始，直到拆成了$n$颗，设此时的$n$颗雷威力是$c_1,c_2,\cdots ,c_n$，则存在其与$a_1,a_2,\cdots ,a_n$的某种匹配$p$，使得$c_{p_i}\ge a_i$。

我们考虑问题：给出猴腮雷的集合$S$与$T$，其中允许在$S$中拆雷，最终要求$S$与$T$有一种上述关系的匹配。原问题就是，$S$只有一个威力为$x$的雷，$T$有$n$个雷，威力为$a_i$。

对于一般的问题$(S,T)$，我们有这样的解决方法：

如果$|S|=|T|$，只需将$S$与$T$分别从小到大（或从大到小）排序，若$S$的对应元素都大于等于$T$的对应元素，则问题$(S,T)$可行，否则不可行。

否则，如果$S$为空，则问题$(S,T)$不可行。

否则，设$S$的最大元素是$s$，$T$的最大元素是$t$。并且，不妨设序列$b$的最小元素是$b_1$。我们根据$s-b_1$与$t$的大小关系选择我们采取的策略：

如果$s-b_1<t$，则在$S$中查找大于等于$t$的最小元素$s_0$，将$s_0$与$t$建立匹配关系（即删除），即问题$(S,T)$的可行性与问题$(S-\{s_0\},T-\{t\})$的可行性相同。如果找不到$s_0$，则问题$(S,T)$不可行。

如果$s-b_1\ge t$，则将$s$拆分成$m$个雷。即问题$(S,T)$的可行性与问题$(S-\{s\}+\{s-b_1,s-b_2,\cdots ,s-b_n\},T)$的可行性相同。

正确性：

对于$s-b_1<t$的情况，由于$t$不可能与$S$的某个元素拆分出来的元素匹配（因为即使是$s-b_1$都无法满足$t$），所以$t$只能与$S$中的某个元素匹配，所以显然要选择一个最小的可行元素。

对于$s-b_1\ge t$的情况，由于$|S|<|T|$，$S$中必然有某个元素要被拆分。假如$s$没有被拆分，任取一个被拆分的元素$s_1$，且$s$最终和$T$中的元素$t_1$匹配。那么，最终拆出来的是$s_1-b_1,s_1-b_2,\cdots ,s_1-b_m$。我们不如不拆$s_1$而拆$s$，将$t_1$改为和$s-b_1$匹配（因为$s-b_1\ge t_1$），最终拆出来的是$s_1,s-b_2,\cdots ,s-b_m$，可以发现这$m$个数对应大于等于之前的$m$个数，所以也不会更差。

时间效率：

$s-b_1<t$至多发生$n$次，因为每发生一次都会删掉$T$中的一个元素。

$s-b_1\ge t$也至多发生$(n-1)/(m-1)$次，因为每发生一次都会让$S$增多$m-1$个元素。

使用multiset维护两个集合，就可以$O(n\log n)$判定一个问题$(S,T)$是否可行。

总的时间复杂度是$O(n\log n\log U)$，可以获得100分。

vfk：“好像很帅的样子”

后记

这道题的灵感来自于清华集训2015的King一题，其中有一个测试点需要解决这个问题的$a_i$全相等，$b=\{1,2\}$的版本。后来经过自己的各种乱搞和推广，变成了这个样子。

而且，这道题最初的模样并不是保证$(n-1)mod(m-1)=0$的，最后可以剩下若干个雷，要求威力最大的雷的威力最小。不过这样的话，二分答案的色彩就过于明显了，所以就改成了这个样子。

本来这道题是我想放到某个NOIP模拟赛里面的，但是想来感觉有点意思，就推荐给了vfk，然后vfk一开始也表示不太会……嗯，幸亏没有扔到NOIP模拟赛里面。

以及，为什么“为了方便，不必输出方案”呢？

因为输出方案实在实在是太太太太麻烦了。有多麻烦呢？标程我写了1.2k，输出方案的话估计至少要翻一番了吧。这道题的亮点在于二分答案和逆向思维，所以强行增加代码量也不是什么好事。

具体的方法就是要在上面的过程中再把分割树全部建出来，我想大家应该都会。

那么，就这样。

新年的贺电

from ppfdd，题目是 vfleaking 造的，题解也是 vfleaking 写的。

题意是要你实现一个传输协议，发送方发送一个 map<unsigned, unsigned>，使得接收方可以查询 map 里的值，且传输的长度要尽量短。

算法一

注意到 $n\le 43008$ 的时候每个测试点可以拿 $2$ 分！

就直接把键和值编码发过去就行了。需要 $(32+10)\times 1024=43008$ 个 bit。

可以获得 $20$ 分。

算法二

对于 30% 的数据，$0\le k<1024$。

这种情况下我们可以传 “键为 $0$ 的时候值是多少？”，“键为 $1$ 的时候值是多少？”，“键为 $2$ 的时候值是多少？”……

需要 $10\times 1024=10240$ 个 bit。

可以获得 $30$ 分。

算法三

我想把算法一二贴在一起！

题目没给数据类型？！？！

由于接收方并不能特判数据类型，所以传 map 的时候需要加额外的 bit 来表示数据类型。（然后算法一就挂了）

没关系，我们可以判传的信息的长度对吧，就可以知道数据类型了。

可以获得 $30+14=44$ 分。

算法四

你可以使用哈希！

假设你有一个哈希函数，能把键分别映射到 $[0,1024)$ 中不同的整数上，那么就变成了算法二了。

好，那么怎么找这个哈希函数呢？

考虑直接随机，随机直到可以放进去，然后把随机次数传过去。

只用传一个随机次数，长度一看就很短。

所以！这样就可以…………………………获得 0 分了。

假设是要将 $n$ 个键映射到 $[0,n)$ 的不同的整数，那么期望随机次数是 $\frac{n^n}{n!}=O\left(\frac{e^n}{\sqrt{n}}\right)$ 显然是不可接受的。

算法五

算法四是个很好的思路。仔细思考可以发现我们并不需要哈希一步到位。

我们可以考虑先通过不断随机哈希函数把键值对均匀分成两组，把随机的次数传过去，再递归每一组继续分割。只要发送方和接收方约定好随机哈希函数的随机方式就可以保证双方使用的是同样的哈希函数。

把 $n$ 个元素分成两组的期望随机次数是 $2^n/(\genfrac{}{}{0ex}{}{n}{n/2})=O(\sqrt{n})$，所以时间复杂度是 $T(n)=2T(n/2)+O(n\sqrt{n})=O(n\sqrt{n})$。

至于长度（不算传值的长度），大概是 $L(n)=2L(n/2)+\log \left(2^n/(\genfrac{}{}{0ex}{}{n}{n/2})\right)=O(n)$。

可以获得 50~80 分。

道理我都懂，但是为什么我的输出这么长

你是不是用了定长的编码……

每次要输出次数的时候，你可以先设定一个初始长度 $l_0$，然后传输时先输出 $k-1$ 个 1，再输出一个 0，后面紧跟着一个长度为 $l_0+k$ 的数，这样就可以传不定长的整数了！

本题中我们要传的是随机次数，我们可以根据期望随机次数设定 $l_0$ 然后就可以愉快地传传传了。

算法六

结合一下算法四和算法五，在算法五进行递归的时候递归到 $8$ 就使用算法四进行传输。

这是因为传次数的时候有一定的冗余……

这样可以进一步减少需要用的 bit 数，获得 100 分。

其他算法

比如你可以传每个值对应着哪些键，可以获得 30 分。

比如，你可以不是每次均匀分 2 组，而是直接按照哈希函数分，划分到 $1$ 个元素时停止，然后把划分的过程传过去，可以获得 50~80 分，加上小范围暴力可以获得 80~90 分。

另外，如果是传 $n$ 个键值对，且定义域和值域都是 $[0,2^m)$，那么可以使用插值。你可以选一个略大于 $2^m$ 的素数，在模素数意义下进行运算，这样是 $mn+O(1)$ 个 bit。

而且我们可以达到 $mn$，只要取一个大小为 $2^m$ 的有限域就行了，这个可以通过选取一个不可约多项式得到。这样是 $mn$ 个 bit，易证这是下界。

然而本题中值域和定义域大小不一样，以上两个插值算法就不太妙了……但是我相信还是有只用 $nm$ 个 bit 的算法的。（$m$ 表示值域的长度，即值域为 $[0,2^m)$）（没错，和定义域无关。算法四五六都是如此）

嗯，总之是一道做法花样繁多的通讯题！欢迎大家玩出更优的做法！