自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 23:16:47，当前版本为作者最后更新于2025-05-25 15:23:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

答案是构造所有元素和为 $n$ 倍数的元组。

如果删去的是一对相同的元素，那么因为元组两两不同，一定还会有一个位置不同。否则，剩下的元组元素之和模 $n$ 不同余，所以一定还有不同。所以构造合法。

这样能构造 $n^{m-1}$ 个合法的元组，因为前 $m-1$ 位可以随便选，而第 $m$ 位可以根据前 $m-1$ 位唯一确定。

对于任意合法解，根据鸽笼原理，其最多包含 $n^{m-1}$ 个元组，所以这组构造顶到了合法元组数量上界。

这不是 Ad-Hoc。这个构造方式是可以通过手玩 $n=1,2,3$ 直接导出的。