【AtCoder】ABC283 G - Partial Xor Enumeration

問題のリンク

解法

線形代数の授業でやるような掃き出し法を、 行 列の行列で、左側を上位ビットとみなすイメージでやる。

すると、総XORで作れる要素を昇順に並べたときに 番目に来るような要素について、 の ビット目が経っている場合、基底の（2進数で見たときに）小さい方から 番目を選ぶ感じでやると構成できる。

ビット間の強弱関係（あるビットがたっているときにそれより下位のビットがすべて立っていても2進数で見ると真に小さい）と、基底間の強弱関係（ある基底が含まれるときにその基底より下位の基底たちで作れるどんな要素も総XORは小さくなる）が対応するイメージ。

掃き出しそのものはchmin(v, v ^ b)でできることに思いを馳せると以下のような実装になる。

#include "my_template.hpp"
using namespace std;

int main() {
    INT(N);
    I64(L, R);
    VEC(i64, A, N);
    vector<i64> base;
    REP(i, LEN(A)) {
        // i行目の基底を見つける
        i64 mx = MAX(A);
        if (mx == 0) break;
        // それより上の行の基底を掃き出す
        FORE(b, base) chmin(b, b ^ mx);
        base.push_back(mx);
        // それより下の行の基底を掃き出す(上の行の基底だったものは0になっている)
        FORE(v, A) chmin(v, v ^ mx);
    }
    // ビットの大小関係と基底の大小関係を揃える
    REV(base);
    L--;
    vector<i64> ans;
    REP(k, L, R) {
        i64 e = 0;
        REP(i, LEN(base)) {
            if (k >> i & 1) {
                e ^= base[i];
            }
        }
        ans.push_back(e);
    }
    print(ans);
    return 0;
}

感想

noshi基底はすぐに思いついたためただの基底の組の1つはすぐに求められたが、そこから基底の大小関係とビットの大小関係を対応させること、そしてそのような基底がnoshi基底に少し変更を加える方法や線形代数の授業でやるような普通の掃き出し法で求められることがわからなかった。