您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 3949 XOR：高斯消元求線性基與第 K 小異或值

編輯：C++ 入門

HDU 3949 XOR：高斯消元構建線性基

給定 n 個數，求其子集異或和中第 k 小的值。核心是高斯消元構建線性基，再按二進制位貪心查詢。

線性基構建

從高位到低位（62~0），尋找當前位為 1 的向量作為基向量，消去其他向量該位。最終得到 k 個基向量，互不相干（各最高位不同）。

void Gaussian() {
    int k = 0;
    for (ll j = 1ll<<62; j; j >>= 1) {
        int i = k+1;
        for (; i <= n; i++) if (a[i] & j) break;
        if (i == n+1) continue;
        swap(a[i], a[++k]);
        for (i = 1; i <= n; i++) if (i != k && (a[i] & j)) a[i] ^= a[k];
    }
    zero = (k != n); // 是否存在 0 向量
    n = k;
}

第 K 小查詢

若存在 0 向量，第 1 小為 0，故 k--。將 k 二進制展開，從高位到低位，若對應位為 1 則異或該基向量：

ll query(ll x) {
    x -= zero;
    if (!x) return 0;
    ll res = 0;
    for (int i = n; i; i--) {
        if (x & 1) res ^= a[i];
        x >>= 1;
    }
    return x ? -1 : res; // x 還有剩餘位說明超出範圍
}