Exclusive OR(线性基、FWT)

题目链接：https://ac.nowcoder.com/acm/contest/5667/E
题目描述：
给n个整数A1~An，从n个数中可重复的选i个数出来，算它们的异或和，能得到最大值就是答案。
解题思路：
这个题首先考虑i>19的时候有ansi=ansi-2，证明也很简单，首先 只需要在ansi的基础上再随便挑一个数异或两次就可以了。然后如果i>19之后，如果ansi>ansi-2，则至少需要i-1个数才能达到满秩，而这里i-1至少为19，但题目保证最大秩为18，这两者是矛盾的。
对于ansi(i<=19)，如果A数组储存所有输入进来的数，B数组从1到1<<18，B[i]不等于0就说明i这个数可以得到，那么让B一直连续做异或卷积就行了。(异或卷积可以算下标i^j=n的aiaj)对第i次异或来说，B储存的就是选i-1个数进行异或的所有结果，然后再跟原始数组异或卷积一下就得到了选i个数进行异或的全部情况）
*代码中细节进行了注释：**
代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+7;
int a[1 << 18], b[1 << 18], n;
int N;
int ans[MAXN];
void get() {
    for(int i = 0; i < n; i++) a[i]*=b[i];
}
void fwtxor(int *f, bool inv)
{
    for(int m = 2, half = 1; m <= n; half <<= 1, m <<= 1)
        for(int j=0;j<n;j+=m)
            for(int i=0; i <= half-1; i++)
            {
                int v=f[i+j+half];
                f[i+j+half]=f[i+j]-v,f[i+j]+=v;
                if(inv) f[i+j]/=2,f[i+j+half]/=2;
            }
}
int main()
{
    scanf("%d",&N); n = (1 << 18);
    for(int i = 0; i < N; i++) {
        int u; scanf("%d",&u);
        a[u] = b[u] = 1;
        ans[1] = max(ans[1], u);
    }
    fwtxor(b, 0);
    for(int i = 2; i <= 20; i++) {
        fwtxor(a, 0); get(); fwtxor(a, 1);
        for(int j = 0; j < n; j++) {        //这里之所以从0到n-1是为了检查如果a[i]数很大要及时变成1，否则怕后面乘上b以后超过int，数可能就不对了。
            if(a[j]) {
                a[j] = 1;
                ans[i] = max(ans[i], j);
            }
        }
    }
    for(int i = 20; i <= N; i++)
        ans[i] = ans[i - 2];
    for(int i = 1; i <= N; i++)
        printf("%d ",ans[i]);
}