haar_lib/linalg/mod_2/
determinant.rs

1//! 行列式 (mod 2)
2use crate::ds::bitset::*;
3
4/// mod 2上で行列式を求める
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}