Erdos-Ginzburg-Ziv 定理
Erdos-Ginzburg-Ziv Theorem
对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。
形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$
Proof 1
接下来给一种初等证明。
引理 1：若 EGZ 定理对 $n,m$ 分别成立，则其对 $nm$ 成立。
证明：考虑任意 $2nm-1$ 个整数 $a_1,\dots,a_{2nm-1}$，首先取出 $n-1$ 个数，从剩下的数中取出 $n$ 个，我们可以从这 $2n-1$ 个数中找出 $n$ 个数使其和为 $n$ 的倍数，这样就又留下了 $n-1$ 个数，重复这个过程，我们可以得到 $2m-1$ 个数 $s_1,\dots,s_{2m-1}$，其均为 $n$ 的倍数。对于 $\dfrac{s_1}{n},\dots,\dfrac{s_{2m-1}}{n}$，我们可以找出 $m$ 个数使其和为 $m$ 的倍数。于是我们从 $2nm-1$ 个数中找到了 $nm$ 个数和为 $nm$ 的倍数。$\blacksquare$
由引理 1，我们只需要证明 EGZ 定理对于质数 $p$ 成立即可。
接下来的所有运算在 $\mathbb F_p$ 上进行。
引理 2：$2\le n\le p$，若大小为 $2n-1$ 的可重集 $A$ 中不存在 $n$ 个相同的数，令 $S$ 为 $A$ 中任意 $n$ 个数的和构成的不可重集合，有 $|S|\ge n$。
证明：对 $n$ 归纳。$n=2$ 的情况是 trivial 的。
现在假设引理对 $n$ 成立，下证其对 $n+1$ 成立。
考虑大小为 $2n+1$ 的可重集 $A'=\{a_1,\dots,a_{2n-1},b,c\}$，不妨设 $b,c$ 为 $a_1,\dots,a_{2n-1}$ 中出现次数最多的两个数，$b\ne c$。$A'$ 中没有数出现了 $\ge n+1$ 次，则 $A=\{a_1,\dots,a_{2n-1}\}$ 没有数出现了 $\ge n$ 次，否则 $A'$ 中除 $b,c$ 外还有数出现了 $n$ 次，即至少三个数出现了 $n$ 次，这显然是不可能的。
根据归纳假设，我们可以从 $A$ 中取出 $n$ 个子集，其元素和不同，设这些和为 $s_1,\dots,s_n$。设 $B=\{s_i+b\},C=\{s_i+c\}$，若 $B\ne C$，则引理得证，否则 $B$ 和 $C$ 的元素和相同，即 $n(b-c)=0$，由于 $p$ 是质数，$n,(b-c)$ 非零，于是这与假设矛盾。$\blacksquare$
接下来考虑分两种情况讨论。
- 在 $2p-1$ 个数中有一个数出现了不少于 $p$ 次，则这 $p$ 个数的和就是 $p$ 的倍数。
- 否则，通过引理 2 可知，$|S|\ge p$，事实上 $S$ 构成模 $p$ 的完全剩余系，故可以找到 $p$ 个数是 $p$ 的倍数。
综上，定理得证。$\blacksquare$
Proof 2
为了加深对定理的认识，这里还有另外一种证法。
证明的主体是相似的，我们直接来考虑规模为质数 $p$ 且没有数出现了不少于 $p$ 次的情况。
此时，我们总是可以将 $2p-1$ 个数分成 $p-1$ 组两数不等的数对和一个单独的数，事实上引理 2 就是做了这件事情。我们先选中单独的数和每组数中较小的那个，这样我们就已经选出了 $p$ 个数，只不过和可能不是 $p$ 的倍数。接下来我们会说明，我们可以通过调整一些组的选择方案而使总和成为 $p$ 的倍数。
将每组中的两数作差，问题转化为：从 $p-1$ 个非 $0$ 整数中选取若干个，使其和模 $p$ 等于 $r$。
我们可以证明，$p-1$ 个非 $0$ 整数的所有子集和模 $p$ 的值构成的集合大小为 $p$，也就是构成了模 $p$ 的完系，这样自然上述问题总能解决。
我们考虑动态维护一个集合 $S$ 和一个数集 $A$，保证 $S$ 中的数都可以通过 $A$ 的子集和模 $p$ 得到（反之则未必成立）。初始 $S=\{0\},A=\varnothing$，接下来我们将 $p-1$ 个数逐个加入 $A$。
向 $A$ 中加入 $x$ 时，考虑长度为 $p$ 的序列 $a_{0\dots p-1}$，其中 $a_k=kx$，由于 $x$ 非 $0$ 且 $p$ 是质数，所以 $a_k$ 取遍 $0\sim p-1$。因为 $a_0\in S$ 且 $\exists k,a_k\not\in S$，所以总有 $k$ 使得 $a_k\in S \land a_{k+1}\not \in S$，此时只要将 $x$ 和组成 $kx$ 的数拼起来，就可以将 $S$ 的大小扩大 $1$。重复此过程 $p-1$ 次后，$S$ 的大小恰好为 $p$。$\blacksquare$
Related Problems
CF1798F Gifts from Grandfather Ahmed
对 EGZ 定理的简单运用，题目的数据范围允许从 $2n-1$ 个数中通过暴力背包 $O(n^3)$ 找出想要的 $n$ 个数。使用 std::bitset 则可以方便的做到 $O(n^3/w)$。
本题要求对 EGZ 定理给出一个高效的构造算法。
按照 Proof 1 的证明，我们可以给出一个构造算法，只需要做一个类似背包的操作即可。可以通过 std::bitset 做到 $O(n^2/w)$，另外由于在可达性背包问题中，每个位置值只会发生一次修改，可以基于此给出均摊的线段树 + hash 或 bit + 二分 + hash 做法，复杂度为 $O(n\log^2 n)$，但线段树做法常数较大，难以通过本题。
按照 Proof 2 的证明，我们只需要实现那个寻找 $kx\in S,(k+1)x \not\in S$ 的操作即可，这可以通过二分实现，复杂度 $O(n\log n)$。（arXiv:2208.07728 详细呈现了这个算法）
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
