题解 P4869 【albus就是要第一个出场】

wrpwrp · 2020-06-16 09:09:20 · 题解

这题貌似没人给出一个正常的证明，所以给一个比较好理解的证明。

设n个数的线性基里面有k个数，那就有n- k个数不在线性基里面。考虑分类讨论一下。 先说明，对于一个异或和，在外面n - k个数中任意取一个数加入异或出这个异或和的数的集合，一定可以通过调整集合内在原本的线性基内的数的组成来使异或和不变。

• 如果从外面加入的这个数可以用除了表示出这个异或和的那些线性基内的数表示出来，那就把那些数也异或进来，那么异或和不变。
• 如果外面加入的数必须用完全属于表示出这个异或和的那些线性基内的数表示出来，那就不选这些数，那异或和还是不变。
• 如果部分属于表示这个集合的数，部分不属于，那就把两个部分拆开，属于的部分不选，不属于的部分选，就把这两个部分都变成了0，异或和还是不变。

那么如果从外面n - k个数中选多于一个数，那么对于每一个数都按照一个数的操作方法就可以保证异或和不变。所以对于外面的点的任意一个集合都是可以通过调整线性基内的数使得异或和不变。所以同一个异或和出现了2^{n - k}次。

代码太丑了就不贴了　（其实是我懒得写了