competitive/algorithm/
xorbasis.rs

1/// Basis of xor operation.
2#[derive(Debug, Clone, Default)]
3pub struct XorBasis {
4    /// (reduced basis, coordinates, inserted basis)
5    bases: Vec<(u64, u64, u64)>,
6}
7impl XorBasis {
8    /// Create a empty space.
9    pub fn new() -> Self {
10        Default::default()
11    }
12    /// Return (reduced basis, coordinate).
13    /// Coordinate means if i-th bit is 1, x was reduced by i-th inserted basis.
14    pub fn reduce(&self, mut x: u64) -> (u64, u64) {
15        let mut coord = 0u64;
16        for (i, (u, c, _)) in self.bases.iter().enumerate() {
17            if x > u ^ x {
18                coord ^= c ^ (1 << i);
19                x ^= u;
20            }
21        }
22        (x, coord)
23    }
24    /// Return true if inserted element cannot be consisted by current basis and be added as a new basis.
25    /// Return false if inserted element can be consisted by current basis.
26    pub fn insert(&mut self, x: u64) -> bool {
27        let (y, coord) = self.reduce(x);
28        if y != 0 {
29            self.bases.push((y, coord, x));
30        }
31        y != 0
32    }
33    /// Return coordinate if element can be consisted by current basis.
34    pub fn find(&self, x: u64) -> Option<u64> {
35        let (y, coord) = self.reduce(x);
36        if y == 0 { Some(coord) } else { None }
37    }
38    /// Return coordinate if element can be consisted by current basis.
39    pub fn basis(&self, x: u64) -> Option<Vec<u64>> {
40        let (y, coord) = self.reduce(x);
41        if y == 0 {
42            Some(
43                self.bases
44                    .iter()
45                    .enumerate()
46                    .filter_map(|(i, (_, _, b))| {
47                        if coord & (1 << i) != 0 {
48                            Some(*b)
49                        } else {
50                            None
51                        }
52                    })
53                    .collect(),
54            )
55        } else {
56            None
57        }
58    }
59}
60impl std::iter::FromIterator<u64> for XorBasis {
61    fn from_iter<T: IntoIterator<Item = u64>>(iter: T) -> Self {
62        let mut basis = XorBasis::default();
63        for x in iter {
64            basis.insert(x);
65        }
66        basis
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73    use crate::{rand, tools::Xorshift};
74
75    #[test]
76    fn test_xor_basis() {
77        let mut rng = Xorshift::default();
78        const Q: usize = 200;
79
80        for _ in 0..Q {
81            let mut basis = XorBasis::new();
82            for x in rng.random_iter(0u64..).take(Q) {
83                if let Some(b) = basis.basis(x) {
84                    assert_eq!(x, b.into_iter().fold(0, std::ops::BitXor::bitxor));
85                }
86                basis.insert(x);
87            }
88        }
89    }
90
91    fn consistables(b: &[u64]) -> std::collections::HashSet<u64> {
92        assert!(b.len() <= 20);
93        (0..1 << b.len())
94            .map(|i| {
95                b.iter()
96                    .enumerate()
97                    .map(|(j, &b)| if i & (1 << j) != 0 { b } else { 0 })
98                    .fold(0, std::ops::BitXor::bitxor)
99            })
100            .collect()
101    }
102
103    #[test]
104    fn test_xor_basis_find() {
105        let mut rng = Xorshift::default();
106        const Q: usize = 100;
107        const L: usize = 12;
108
109        for _ in 0..Q {
110            rand!(rng, k: 0usize..=L + 2, b: [0u64..1 << L; k]);
111            let cons = consistables(&b);
112            let basis: XorBasis = b.into_iter().collect();
113            for x in rng.random_iter(0u64..1 << L).take(Q) {
114                assert_eq!(cons.contains(&x), basis.find(x).is_some());
115            }
116        }
117    }
118}
competitive/algorithm/xorbasis.rs

competitive/algorithm/
xorbasis.rs
