library_checker/linear_algebra/system_of_linear_equations_mod_2.rs
1use competitive::prelude::*;
2use competitive::{data_structure::BitSet, math::BitMatrix};
3
4#[verify::library_checker("system_of_linear_equations_mod_2")]
5pub fn system_of_linear_equations_mod_2(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, _m, a: [@BitSet::from_binary; n], b: @BitSet::from_binary);
8 let a = BitMatrix::from_vec(a);
9 if let Some(sol) = a.solve_system_of_linear_equations(&b) {
10 pp!(sol.basis.len());
11 for row in std::iter::once(sol.particular).chain(sol.basis) {
12 pp!(row.to_binary());
13 }
14 } else {
15 pp!(-1);
16 }
17}