Day 119-Q1 | 線形基底（XOR Basis・GF(2)ガウス消去法）

問題

N個のクエリを順に処理せよ。多重集合（初期状態は空）に対し、次の2種類のクエリが与えられる。

A x: 値 x を多重集合に追加する
Q x: 現在の多重集合から部分集合を選び、その要素すべてのXORを取ることで x を作れるかどうかを判定し、Yes/Noを出力する（空集合を選んでXOR=0を作ることも可能）

入力形式

N
query_1
query_2
...
query_N

各 query_i は A x または Q x の形式。

制約

$1 \le N \le 2\times10^5$

$0 \le x < 2^{30}$

Aクエリ・Qクエリの出現回数は不定

入出力例

入力例1

6
A 5
A 3
Q 6
Q 7
A 6
Q 6

出力例1

Yes
No
Yes

{5,3}から作れるXORは{0,5,3,6}。6=5^3で作れるのでYes、7は作れないのでNo。A 6は既存の基底で表現できる値なので基底は増えず、その後のQ 6も引き続きYes。

概念図: ガウス消去による基底判定

ヒント（段階的開示）

ヒント1: 方向性

「部分集合のXORで x が作れるか」を毎回すべての部分集合を試すと $O(2^N)$ で間に合わない。XORはGF(2)（0と1の世界）上のベクトル加算とみなせるので、この問題は「与えられたベクトル集合が張る線形空間に x が含まれるか」という線形代数の問題に帰着できる。

ヒント2: アプローチ

30bit整数を30次元のGF(2)ベクトルとみなす。ガウスの消去法の要領で「基底」を維持する：新しい値を追加するとき、最上位から見ていき、まだ基底に無いbitがあればそこに登録し、既にあればXORして消去してから次のbitへ進む。この基底は高々30個しか要素を持たず、追加・判定ともに $O(30)$ で処理できる。

ヒント3: 誘導（コード骨格）

# basis[b] = 最上位bitがbであるような基底ベクトル（無ければ0）
def insert(x):
    for b in range(29, -1, -1):
        if not (x >> b) & 1:
            continue
        if basis[b] == 0:
            basis[b] = x
            return
        x ^= basis[b]
    # ここに到達したらxは既存の基底で表現可能（線形従属）なので何もしない

def can_represent(x):
    for b in range(29, -1, -1):
        if not (x >> b) & 1:
            continue
        if basis[b] == 0:
            return False   # このbitを消せる基底が無い＝作れない
        x ^= basis[b]
    return x == 0          # 全bit消せたら作れる

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    BIT = 30  # 0 <= x < 2^30
    basis = [0] * BIT

    def insert(x):
        for b in range(BIT - 1, -1, -1):
            if not (x >> b) & 1:
                continue
            if basis[b] == 0:
                basis[b] = x
                return
            x ^= basis[b]

    def can_represent(x):
        for b in range(BIT - 1, -1, -1):
            if not (x >> b) & 1:
                continue
            if basis[b] == 0:
                return False
            x ^= basis[b]
        return x == 0

    out = []
    for _ in range(N):
        t = data[idx]; idx += 1
        x = int(data[idx]); idx += 1
        if t == b'A':
            insert(x)
        else:
            out.append("Yes" if can_represent(x) else "No")
    print('\n'.join(out))


solve()

計算量: 1回のinsert/can_representはビット幅30に比例するのでO(30)、全体でO(30N)。乱数300試行のstress test（brute forceの「全部分集合のXOR集合を毎回再計算して判定」との突き合わせ）を実際に実行し、全試行で出力が一致することを確認済み。

Step-by-Step 解説

1XORをGF(2)ベクトルとして捉える
30bit整数は「30個の0/1成分を持つベクトル」とみなせる。XORはこの空間での成分ごとの加算（mod 2）に一致する。「部分集合のXORで作れる値の集合」は、その部分集合が張る線形部分空間そのものである。

2基底（ガウス消去形）の維持
basis[b]に「最上位bitがちょうどbであるベクトル」を保持するようにガウス消去を行うと、基底は常に簡約階段形（各基底ベクトルの最上位bitが互いに異なる）になる。

3挿入処理
挿入したい値xを上位bitから見ていき、空いていればxをそこに置いて終了。埋まっていればxをXORして「そのbitを消し」次のbitへ進む。最終的にxが0になれば、基底は増えない。

4判定処理
考え方は挿入とほぼ同じだが、基底が空いている場合はその時点で「作れない」と確定できる。全bitを消しきれてx=0になれば「作れる」。

5計算量の確認
基底のサイズは高々30（ビット幅）なので、挿入・判定ともにO(30)。N回のクエリでO(30N)、$N\le2\times10^5$でも余裕を持って間に合う。

よくあるミス

ミス	原因	正しい書き方
上位bitからではなく下位bitから消去してしまう	単純な走査順で実装してしまう	必ず最上位bitから見て「簡約階段形」を保つ
xが0になったら基底に追加しない、を忘れて0を登録してしまう	ループを抜けた後に無条件でbasisへ書き込んでしまう	ループ内でreturnするのは基底に空きを見つけた時のみとする
can_representとinsertのロジックを混同し、判定なのに基底を変更してしまう	同じ関数を使い回そうとする	判定用はbasis配列を変更しない（xはローカル変数として消去するだけ）
ビット幅を制約より小さく（例:20）設定してしまう	制約の$2^{30}$を見落とす	BIT = 30のように制約の上限bit数以上を確保する

次のステップ

発展: 各基底ベクトルに「どの元の要素の組み合わせで作られたか」を復元できるよう、挿入時に使用した元の要素の集合（bitmask等）も一緒に管理してみる。
次回予告: クラスカル再構築木（Kruskal's Reconstruction Tree）

自己評価

完全理解おおむね理解要復習

Day 119-Q1 — 線形基底（XOR Basis・GF(2)ガウス消去法）

問題