Exclusive OR

题意

个数, 求从中取出个数的最大异或和，输出的答案

题解

FWT：
这是一个卷积的形式，只不过平常的卷积运算符是
我们用记录中是否出现
那么代表的含义就是

选取两个数的异或值为的种数

同理，代表的含义为

在选取了个数能得到的异或和数中选取一个，在初始数字中选取一个, 使得的种数

所以这就是一个FWT的题
但是我们不需要知道取得的方案数有多少种，我们只关心能不能取到，所以每次卷积完之后，都将能取到的设为

另外当的情况，题目说的比较清楚了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;

int N;
int a[1 << 18], b[1 << 18], n;
int ans[MAX];

void get() { for (int i = 0; i < n; i++) a[i] *= b[i]; }

void XOR(int *f, int x = 1) {
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++) {
                int a0 = f[i + j], a1 = f[i + j + k];
                f[i + j] = a0 + a1;
                f[i + j + k] = a0 - a1;
                if (x == -1) {
                    f[i + j] /= 2;
                    f[i + j + k] /= 2;
                }
            }
}


int main() {

    scanf("%d", &N); n = 1 << 18;
    for (int i = 1; i <= N; i++) {
        int x; scanf("%d", &x);
        a[x] = b[x] = 1;
        ans[1] = max(ans[1], x);
    }
    XOR(b,1);
    for (int i = 2; i <= 20; i++) {
        XOR(a, 1); get(); XOR(a, -1);
        for (int j = 0; j < n; j++)
            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]);

    return 0;
}