【精進8】ZONe 2021-F

XOR基底シリーズ

問題

$N=2^n$頂点がある。長さ$M$の列$A$が与えられ、任意の$i$について$s\oplus t \ne A_i$のとき頂点$s,t$間に辺を張ることができる。連結にできるか判定し、できるなら$1$つ辺の貼り方を出力せよ。

解法

$A$よりも$A$にない数に注目する。$B$を$0$以上$N$未満の数であって$A$のどの要素とも異なるものの集合とする。$B$の張る空間 $X(B)=\lbrace\bigoplus_{s\in S}s \mid{S\subseteq B}\rbrace$ の基底であって、$B$の部分集合となるものの$1$つを$\mathrm{basis}(B)$と書く。 このとき頂点$0$と連結にできる集合は$X(B)$である。実際$x\in X(B)$について次のように辺を構成できる。まずある$E \subseteq \mathrm{basis}(B)\subseteq B$について$x=\bigoplus_{e\in E}e$と書ける。$E=\lbrace e_1,\dots,e_K\rbrace,e_0=0$と置き、$t_i=\bigoplus_{j\le i}e_j$とすると、各$i$について$t_i\oplus t_{i+1}=e_{i+1}\in B$であるから頂点$t_i,t_{i+1}$間に辺を貼れる。$t_0=0,t_K=x$であるから$0$と$x$を連結となるように辺を張ることができた。また任意の$s\not\in X(B),x\in X(B)$について$s\oplus x\not\in B$となるから$0$と$s\not \in X(B)$は連結にできない。従って$|X(B)|=N$が連結にできる条件である。辺の構築については、順に$X,\mathrm{basis}$を構築する中で、$\mathrm{basis}$が増えた際に元の$X$の要素$x$と$e_{\mathrm{new}}\oplus x$間に辺を張っていけばよい。

#include "template.hpp"
void solve() {
    LL(n, m);
    vl a(n, 0);
    rep(i, m) {
        LL(ai);
        a[ai]++;
    }
    vl basis;
    vector<P> ans;
    vl x = {0}; // 0と連結な頂点の集合
    auto in = [&](const ll num) {
        ll e_new = num;
        for(auto &e : basis)
            chmin(e_new, e_new ^ e);
        if(e_new == 0)
            return;
        basis.push_back(e_new);
        ll sz = x.size();
        rep(i, sz) {
            ans.push_back({x[i], x[i] ^ num});
            x.push_back(x[i] ^ num);
        }
    };
    rep(i, n) {
        if(a[i] == 0)
            in(i);
    }
    if(x.size() < n) {
        print(-1);
    } else {
        for(auto &[i, j] : ans) {
            print(i, j);
        }
    }
}

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