library_checker/linear_algebra/
matrix_rank_mod_2.rs

1use competitive::prelude::*;
2use competitive::{data_structure::BitSet, math::BitMatrix};
3
4#[verify::library_checker("matrix_rank_mod_2")]
5pub fn matrix_rank_mod_2(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m);
8    // Transpose very tall matrices to avoid allocating millions of short rows.
9    let transpose = n / 2 > m;
10    let mut a = BitMatrix::zeros(if transpose { (m, n) } else { (n, m) });
11    if transpose && m >= 64 {
12        let mut words = vec![0u64; m];
13        for first in (0..n).step_by(64) {
14            words.fill(0);
15            for i in 0..64.min(n - first) {
16                sc!(row: &str);
17                for (word, b) in words.iter_mut().zip(row.bytes()) {
18                    *word |= u64::from(b == b'1') << i;
19                }
20            }
21            for (row, &word) in a.data.iter_mut().zip(&words) {
22                row.words_mut()[first / 64] = word;
23            }
24        }
25    } else {
26        for i in 0..if m == 0 { 0 } else { n } {
27            sc!(row: &str);
28            if !transpose {
29                a.data[i] = BitSet::from_binary(row).unwrap();
30            } else {
31                for (j, b) in row.bytes().enumerate() {
32                    a[j].words_mut()[i / 64] |= u64::from(b == b'1') << (i % 64);
33                }
34            }
35            if transpose
36                && i == 63
37                && BitMatrix::new_with((m, 64), |row, col| a[row].get(col)).rank() == m
38            {
39                pp!(m);
40                return;
41            }
42        }
43    }
44    pp!(a.rank());
45}
library_checker/linear_algebra/matrix_rank_mod_2.rs

library_checker/linear_algebra/
matrix_rank_mod_2.rs
