XOR 基底

整数を $\mathbb{F}_2$ 上のベクトルとみなし、掃き出し法で最上位ビットが互いに異なる基底を持ちます。いくつかを選んで XOR したときに作れる値の集合が分かります。

• XorBasis(): 空の基底で初期化
• add(x): $x$ を加える。 $x$ が今までの値の XOR で作れず、基底が増えたときは True。 $O(\log A)$
• can_make(x): 今までの値からいくつかを選んで XOR すると $x$ になるか（何も選ばないと $0$）。 $O(\log A)$
• max_xor(x): $x$ に、今までの値からいくつかを選んで XOR したときの最大値（ $x$ の既定は $0$）。 $O(\log A \log \log A)$
• len(b): 基底の大きさ（ランク）。作れる値は $2^{\mathrm{rank}}$ 通り

ここで $A$ は値の最大値です。

コード

class XorBasis:
    def __init__(self):
        self.basis = []  # どの 2 つも最上位ビットが異なる

    def add(self, x):
        # x を加える。x が今の基底の XOR で作れなかったら True
        for b in self.basis:
            x = min(x, x ^ b)
        if x == 0:
            return False
        self.basis.append(x)
        return True

    def can_make(self, x):
        # x が基底のいくつかの XOR で作れるか（何も選ばないと 0）
        for b in self.basis:
            x = min(x, x ^ b)
        return x == 0

    def max_xor(self, x=0):
        # x に基底のいくつかを XOR してできる最大値
        for b in sorted(self.basis, reverse=True):
            x = max(x, x ^ b)
        return x

    def __len__(self):
        return len(self.basis)