碰碰车大战 题解

· · 题解

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

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

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

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

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