题解 | #异或#

记录线性基每一个基是由偶数个元素异或组成还是奇数个元素异或组成即可。令 ans[0/1] 表示偶数或奇数时的答案，跑一遍 DP。若当前枚举到的基由偶数个元素组成，则 ans[0] 从 ans[0] 转移，ans[1] 同理；若当前枚举到的基由奇数个元素组成，则 ans[0] 从 ans[1] 转移，ans[1] 同理。

若存在两个基既存在奇数个元素的构成方式又存在偶数个元素的构成方式，那么显然奇数和偶数两种情况的答案是相同的，直接朴素求最大值即可。

#include <cstdio>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
const int N = 2001;

int n;
bitset<N> a[N], ans[2], nowbs;
bool both, odd[N];
char s[N];

bool cmp(const bitset<N> &a, const bitset<N> &b){
    for (int i = N - 1; i >= 0; i--)
        if(a[i] != b[i])
            return a[i] < b[i];
    return false;
}

int main(){
    scanf("%d", &n);
    while(n--){
        scanf("%s", s);
        bitset<N> bs(s);
        int now = 1;
        for (int i = strlen(s) - 1; i >= 0; i--)
            if(bs[i]){
                if(!a[i][i]){
                    a[i] = bs;
                    odd[i] = now;
                    break;
                }
                else if(a[i] != bs){
                    bs = bs ^ a[i];
                    now ^= odd[i];
                }
                else{
                    if(now ^ odd[i])
                        both = true;
                    break;
                }
            }
    }
    if(both){
        for (int i = N - 1; i >= 0; i--)
            if(a[i][i] && !ans[0][i])
                ans[0] ^= a[i];
        ans[1] = ans[0];
    }else{
        bool now = 0, nowboth = 0, first = false;
        for (int i = N - 1; i >= 0; i--){
            if(a[i][i]){
                if(!first){
                    ans[1] = a[i];
                    first = true;
                    continue;
                }
                else if(odd[i]){
                    bitset<N> tmp[2];
                    tmp[0] = ans[0];
                    tmp[1] = ans[1];
                    if(cmp(ans[0], tmp[1] ^ a[i]))
                        ans[0] = tmp[1] ^ a[i];
                    if(cmp(ans[1], tmp[0] ^ a[i]))
                        ans[1] = tmp[0] ^ a[i];
                }else{
                    if(cmp(ans[0], ans[0] ^ a[i]))
                        ans[0] = ans[0] ^ a[i];
                    if(cmp(ans[1], ans[1] ^ a[i]))
                        ans[1] = ans[1] ^ a[i];
                }
            }
        }
    }
    for (int i = 0; i < 2; i++){
        bool flag = false;
        for (int j = N - 1; j >= 0; j--){
            if (ans[i][j])
                flag = true;
            if (flag)
                printf("%d", (int)ans[i][j]);
        }
        if (!flag)
            putchar('0');
        putchar('\n');
    }
    return 0;
}