利用高斯消元来判断向量能否被前面的向量张成

我们每次维护一个对角矩阵。执行到第 ii 步的时候，我们从高到低考虑数 a_ia​i​​ 为 11 的二进制位 jj，如果 jj 这一行的对角线已经为 11 了，那么我们不能加入，同时为了保持上三角性质，需要将第 jj 行的行向量异或到 \mathbf{a}_ia​i​​；如果 jj 这一行的对角线为 00，那么我们就可以将 \mathbf{a}_ia​i​​ 添加到这一行，同时为了维护一个对角矩阵，要先用下面的行消自己，再用自己消上面的行。

 

 

 

 

 

例题 HDU 3949 XOR

注意不存在的条件 以及能否凑出0

#pragma warning(disable:4996)

#include<iostream>
#include<algorithm>
//#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define INF 0x3f3f3f3f
#define inf 0x7FFFFFFF
#define MOD 1000000007
#define moD 1000000003
#define pii pair<string,int>
#define eps 1e-7
#define equals(a,b) (fabs(a-b)<eps)
#define bug puts("bug")
#define re  register
#define fi first
#define se second
const int maxn = 1e4 + 5;
const double Inf = 10000.0;
const double PI = acos(-1.0);
typedef  long long ll;
using namespace std;

const int max_base = 63;

int n;

ll a[maxn];
ll b[max_base+5];
vector<ll> v;

bool flag;

void cal() {
    int cnt = 0;
    memset(b, 0, sizeof b);
    for (int i = 0; i < n; ++i)
        for (int j = max_base; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i] , cnt++;
                    for (int k = j - 1; k >= 0; --k) if (b[k] && ((b[j] >> k) & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= max_base; ++k) if ((b[k] >> j) & 1) b[k] ^= b[j];
                    break;
                }
            }

    v.clear();
    for (int i = 0; i <= max_base; i++) {
        if (b[i]) v.push_back(b[i]);
    }
    flag = (n != cnt);
}

ll query(ll k) {
    if (flag) k--;
    //cout << v.size() << "   xxx   " << endl;
    if (k >= (1ll<<v.size())) return -1;
    ll ans = 0;
    for (int i = 0; i < v.size(); i++) if ((k >> i) & 1) ans ^= v[i];
    return ans;
}


int main() {
    int T;
    int kase = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%lld", a + i);
        cal();
        int m;
        scanf("%d", &m);
        printf("Case #%d:\n", kase++);
        while (m--) {
            ll k;
            scanf("%lld", &k);
            ll ans = query(k);
            printf("%lld\n", ans);
        }
    }
}