haar_lib/linalg/mod_2/
determinant.rs

1//! $\mathbb{Z} / 2 \mathbb{Z}$上の行列式
2use crate::ds::bitset::*;
3
4/// $\mathbb{Z} / 2 \mathbb{Z}$上で行列式を求める。
5pub fn determinant(mut a: Vec<Bitset>) -> u64 {
6    let n = a.len();
7
8    assert!(a.iter().all(|r| r.len() == n));
9
10    for i in 0..n {
11        if !a[i].test(i) {
12            if let Some(j) = (i + 1..n).find(|&j| a[j].test(i)) {
13                a.swap(i, j);
14            } else {
15                return 0;
16            }
17        }
18        let ai = a.swap_remove(i);
19
20        for aj in a.iter_mut().skip(i) {
21            if aj.test(i) {
22                aj.same_size_xor_assign(&ai);
23            }
24        }
25
26        a.push(ai);
27        a.swap(i, n - 1);
28    }
29
30    1
31}