CEOI Team Selection D1T2 Prosjek-526互联

首先全奇全偶的情况是容易的，将 \(\bmod4\) 意义下相同的合并即可保持原来的奇偶状态，当只有两个是直接合并即可，归纳即可说明全奇全偶一定合法。
但关键的问题在于奇偶状态可能互相影响，一个直观的想法是将奇合并为一个 \(x\)，偶合并为一个 \(y\)，如果 \(x,y\) 的奇偶性相同，那么它们即可合并，即我们关心奇集合与偶集合最终可以得到的状态。
手玩一些数据可以发现，其实当集合的数比较多元时，一个集合总是既能变为奇，又能变为偶，而 \(\bmod4\) 的奇偶性相同性控制着奇偶性，即我们可以考虑尽可能保持 \(\bmod4\) 意义下每一种形态都存在，而且如果两个集合我们均不能保证每种状态均存在，那么由于我们只能使奇集合变为奇，偶集合变为偶，最终无法将其合并。
不妨设奇集合 \(\bmod4=1,\bmod4=3\) 的均存在，那么每次选择 \(\bmod4=r\) 中 \(\geqslant3\) 的一个操作，即可保证该状态不会改变，且集合的大小 \(\geqslant4\)，我们接下来说明这样的操作不会对答案的存在性产生影响：
当集合大小为 \(2\) 时：必然一开始就为 \(2\)，此时只有唯一方式，即变为偶。
当集合大小为 \(3\) 时：不妨令其为 \(a,b,c\)，且满足 \(a\bmod4=1,b\bmod4=1,c\bmod4=3\)。
\(case1:\) 变为偶，我们可以操作 \(a,b\) 或 \(b,c\) 或 \(a,c\) 变为子状态，可以发现三个中必然有一个是可以变的，否则有 \(\frac{a+b}{2}\bmod4=3,\frac{a+c}{2}\bmod4=1,\frac{b+c}{2}\bmod4=1\)，那么有 \((\frac{a+b}{2}+\frac{a+c}{2})\bmod4=0\)，\((a+\frac{b+c}{2})\bmod4=2\)，而两式本身相等，则导出矛盾，所以必然有一个可以操作变为子状态。
\(case2:\) 变为奇，同理我们可以操作 \(a,b\) 或 \(b,c\) 或 \(a,c\) 变为子状态，可以发现三个中必然有一个是可以变的，否则有 \(\frac{a+b}{2}\bmod4=1,\frac{a+c}{2}\bmod4=3,\frac{b+c}{2}\bmod4=3\)，那么有 \((\frac{a+c}{2}+\frac{b+c}{2})\bmod4=2\)，\((\frac{a+b}{2}+c)\bmod4=0\)，而两式本身相等，则导出矛盾，所以必然有一个可以操作变为子状态。
即其既能变为奇，又能变为偶。
当集合大小为 \(4\) 时：不妨令其为 \(a,b,c,d\)，且满足 \(a\bmod4=1,b\bmod4=1,c\bmod4=3,d\bmod4=3\)，那么如果 \(\frac{a+b}{2}\bmod4=1\) 或 \(\frac{c+d}{2}\bmod4=3\)，则可以变为大小为 \(3\) 的状态，那么则既能变为奇，又能变为偶，在接下来的讨论中，默认 \(\frac{a+b}{2}\bmod4=3\) 或 \(\frac{c+d}{2}\bmod4=1\)。
\(case1:\) 变为偶，我们可以操作 \(a,b\) 与 \(c,d\)，变为大小为 \(2\) 的情况。
\(case2:\) 变为奇，我们可以操作 \(a,b\)，现将其变为 \(e,c,d\) 三个数，其中 \(e\bmod4=3\)，而\(\frac{c+d}{2}\bmod4=1\)，则可以操作 \(e,c\) 或 \(e,d\) 或 \(c,d\) 变为子状态，可以发现三个中必然有一个是可以变的，否则有 \(\frac{e+c}{2}\bmod4=1,\frac{c+d}{2}\bmod4=1,\frac{e+d}{2}\bmod4=1\)，那么有 \((\frac{e+c}{2}+\frac{e+d}{2})\bmod4=2\)，\((e+\frac{c+d}{2})\bmod4=0\)，而两式本身相等，则导出矛盾，所以必然有一个可以操作变为子状态。
对于偶集合的讨论同理，我们即证明了如上的操作不会对答案的存在性产生影响。
现在即要凑上述的状态，可以发现每次操作可以使二进制下最小的差异位减少 \(1\)，而减到不能再减了就合法了，而每次将最小差异位的 \(01\) 操作即可尽量使其减少。
经上述操作，可将元素个数缩为 \(8\) 以内，对剩下的可以跑爆搜。