Playing games

题目：
https://ac.nowcoder.com/acm/contest/295/H

有$n$个数，选出尽量多的数使得异或和为$0$。
$1\le n\le 500000,0\le a_i\le 500000$
思路：
问题等价于选出尽量少的数使得异或和为全部数的异或和$val$。根据线性基思想可以推得整个集合的异或集合可以被不超过$19$个数的异或集合表示.因此答案也不超过$19$。所以可以二分答案。
那么如何判断选$mid$个数能否异或成$val$，可以用生成函数$A={\sum }_{i=0}^{500000}{a}_i{x}^i$，$a_i=1$表示$i$这个数存在，为$0$表示不存在，$A^k$就表示选$k$个，只不过这里是多项式的异或，用$FWT$，而且算$B=A^k$，可以直接算$FWT(B)=FWT(A{)}^k$，这样只要把$A$变成$FWT(A)$，然后对每一位算$k$次幂，再把$FWT(B)$变成$B$就行，类似点值表示法。
还要注意一点，这样会选重复，所以没法直接判断能否刚好选$mid$个数，但是重复的异或会抵消，相当于选的个数少于$mid$，因为是二分判断，所以退而求其次，变成判断能否用少于$mid$个数，那么这样生成函数$a_0=1$，代表可以不选。

总结：
异或的卷积形式和加得到的卷积类似，也可以用生成函数。