【精進4】ABC293-G

線型代数の話

問題

G - Partial Xor Enumeration
長さ$N$の非負整数列$A$が与えられる。$A$から$0$個以上の要素を選び$\mathrm{xor}$をとってできる数の集合を$S$とする。$S$の$i$番目に小さい要素を$s_i$として、$s_L,\dots,s_R$を出力せよ。

制約

$N,R-L \le 2 \times 10^5,A_i\le 2^{60}$

解法

$A_i$が他の要素の$\mathrm{xor}$で表されるとき、$A_i$はあってもなくても変わらない。結局高々$60$個の独立な(すなわち、どの要素も他の要素の$ \mathrm{xor} $で書けない)要素たちが問題となる。解答のためには

• $A=(A_1,\dots ,A_N)$から従属なものを取り除く。
• $s_i$を高速に求める。または$s_i$を求めた後$s_{i+1}$を高速に求める。

が必要。 後者は$2$進数で上から桁DP的な感じかと思ったが、よくよく考えてみると基底をうまく取ることによって$s_i=\bigoplus_{j\in i}e_j$のように表すことができることに気づく。$j \in i$は$i$の$j$bit目が$1$の意味。まず$A$から適当な基底$( e_i )$を取り、$i\ne j$について $e_i \gets \min(e_i,e_i \oplus e_j)$を更新できなくなるまで繰り返す。そして$e$を昇順にソートする。すると$e_i$の$1$が立っている最上位ビットは他の基底だと$0$になる。従って基底の部分集合の$\mathrm{xor}$を取る際${j>i}$の要素の有無を固定すると$e_i$を含む$\mathrm{xor}$は含まないものよりも常に大きくなり、上の性質が成り立つ。下のコードのように力技で求めたが解説によるともっとシンプルに計算できる。

#include "/home/y_midori/cp/library/template.hpp"
void solve() {
    LL(n, l, r);
    vl indep;
    auto in = [&indep](ll num) {
        for(auto i : indep)
            chmin(num, num ^ i);
        if(num == 0)
            return;
        indep.push_back(num);
        bool flag = true;
        while(flag) {
            flag = false;
            rep(i, indep.size()) {
                rep(j, indep.size()) {
                    if(i == j)
                        continue;
                    if(chmin(indep[i], indep[i] ^ indep[j])) {
                        flag = true;
                    }
                }
            }
            sort(rbegin(indep), rend(indep));
            indep.erase(unique(all(indep)), indep.end());
            while(indep.size() and indep.back() == 0)
                indep.pop_back();
        }
    };
    rep(i, n) {
        LL(a);
        in(a);
    }
    sort(all(indep));
    debug(indep);
    for(ll bit = --l; bit < r; bit++) {
        ll ans = 0;
        rep(i, indep.size()) {
            if((bit >> i) & 1)
                ans ^= indep[i];
        }
        cout << ans << " ";
    }
    print();
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}