haar_lib/linalg/mod_2/
inverse.rs

1//! 逆行列 (mod 2)
2use crate::ds::bitset::*;
3
4/// mod 2上で逆行列を求める
5pub fn inverse(mut b: Vec<Bitset>) -> Option<Vec<Bitset>> {
6    let n = b.len();
7
8    assert!(b.iter().all(|r| r.len() == n));
9
10    let mut c = vec![Bitset::new(n); n];
11
12    for (i, c) in c.iter_mut().enumerate() {
13        c.set(i, true);
14    }
15
16    for i in 0..n {
17        let q = (i..n).find(|&j| b[j].test(i))?;
18
19        b.swap(i, q);
20        c.swap(i, q);
21
22        let bi = b.swap_remove(i);
23        let ci = c.swap_remove(i);
24
25        for (bj, cj) in b.iter_mut().zip(c.iter_mut()) {
26            if bj.test(i) {
27                bj.same_size_xor_assign(&bi);
28                cj.same_size_xor_assign(&ci);
29            }
30        }
31
32        b.push(bi);
33        b.swap(i, n - 1);
34        c.push(ci);
35        c.swap(i, n - 1);
36    }
37
38    Some(c)
39}
haar_lib/linalg/mod_2/inverse.rs

haar_lib/linalg/mod_2/
inverse.rs
