XorBasis
クラス · XOR (F2 上の線形) 基底
template <std::unsigned_integral T>
struct XorBasis;
概要
XOR (F2 上の線形) 基底
基底のサイズは T のビット幅 $B$ を超えないため、以下では $B$ を用いて計算量を表す
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空の XOR 基底を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
insert |
$x$ を基底へ追加する。基底を拡張できたら true | $O(B \log B)$ |
reduce |
$x$ を基底で簡約する。$0$ になれば $x$ は基底の張る空間に含まれる | $O(B)$ |
contains |
$x$ が基底の張る空間に含まれるかどうか | $O(B)$ |
max_xor |
$x$ との xor を最大化する値を返す | $O(B)$ |
size |
基底ベクトルの個数を返す | $O(1)$ |
empty |
基底が空なら true を返す | $O(1)$ |