haar_lib/linalg/
xor_basis.rs

1//! $\mathbb{F}_2^{64}$上の要素{$a_1, \dots, a_n$}の張る部分空間の基底を求める。
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc283/tasks/abc283_g>
5
6/// $\mathbb{F}_2^{64}$上の要素{$a_1, \dots, a_n$}の張る部分空間の基底を求める。
7pub fn xor_basis(a: Vec<u64>) -> Vec<u64> {
8    let mut basis = vec![];
9    for mut e in a {
10        for &b in &basis {
11            if e ^ b < e {
12                e ^= b;
13            }
14        }
15        for b in basis.iter_mut() {
16            if e ^ *b < *b {
17                *b ^= e;
18            }
19        }
20        if e != 0 {
21            basis.push(e);
22        }
23    }
24    basis
25}