传送门

题意是给n个数，问从中选1个、2个、3个….数，最大的异或和是多少。选数可以重复。

用一个数组，把出现的数字在数组对应下标处 + 1 .

然后做一次下标为异或运算的卷积。C_i=\sum\limits_{i=j \oplus k}A_j* B_k 

卷一次代表选两个数，卷 n 次就代表选 n 个数。卷积结果C_i若不为零，则i表示可以被异或出来。

因为数字最大只有18位，所以理论上来说18次之后最大数就会出现（每个数至少贡献一位）。但是以防万一可以多整几次。之后最大数就和选 n – 2 个数字是一样了。

优化下标为位二元运算的卷积有一个算法叫：快速沃尔什变换（FWT）。

思想是将原序列 A 构造成一个新的序列 FWT[A] 使得卷积可以变成对应项相乘，把复杂度优化到线性。

关于几种运算的构造方法，记一下结论就可以了。结论在此

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 18) + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv = 0;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return res % mod;
}
void ufwt(int a[], int n)
{
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; k++)
            {
                int f1 = a[j + k];
                int f2 = a[i + j + k];
                a[j + k] = 1ll * (f1 + f2) % mod * inv % mod;
                a[i + j + k] = 1ll * (f1 - f2 + mod) % mod * inv % mod;
            }
}
void fwt(int a[], int n)
{
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; k++)
            {
                int f1 = a[j + k] + a[i + j + k];
                int f2 = a[j + k] - a[i + j + k];
                if(f1 >= mod) f1 -= mod;
                if(f2 < 0) f2 += mod;
                a[j + k] = f1, a[i + j + k] = f2;
            }
}
int a[maxn], b[maxn];
int ans[200005];
int main()
{
    inv = ksm(2, mod - 2);

    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int x; scanf("%d", &x);
        a[x]++; b[x]++;
        ans[1] = max(ans[1], x);
    }
    fwt(a, 1 << 18);

    for(int i = 2; i <= min(n, 22); i++)
    {
        fwt(b, 1 << 18);
        for(int j = 0; j < 1 << 18; j++)
            b[j] = 1ll * b[j] * a[j] % mod;
        ufwt(b, 1 << 18);
        for(int j = 1 << 18; j >= 0; j--)
            if(b[j])
            {
                ans[i] = j;
                break;
            }
    }
    for(int i = 23; i <= n; i++) ans[i] = ans[i - 2];
    for(int i = 1; i <= n; i++)
    {
        printf("%d ", ans[i]);
    }
}