// ---------- begin BitSet ---------- #[derive(Clone, Eq, PartialEq)] struct BitSet { size: usize, a: Vec, } fn bit_size() -> usize { 8 * std::mem::size_of::() } fn quot_rem(n: usize) -> (usize, usize) { let w = bit_size(); (n / w, n % w) } #[allow(dead_code)] impl BitSet { fn new(size: usize) -> Self { let w = bit_size(); BitSet { size: size, a: vec![0; (size + w - 1) / w], } } fn set_at(&mut self, x: usize) { assert!(x < self.size); let (q, r) = quot_rem(x); self.a[q] |= 1 << r; } fn clear_at(&mut self, x: usize) { assert!(x < self.size); let (q, r) = quot_rem(x); self.a[q] &= !(1 << r); } fn get_at(&self, x: usize) -> bool { if x >= self.size { return false; } let (q, r) = quot_rem(x); (self.a[q] >> r) & 1 == 1 } fn any(&self) -> bool { self.a.iter().any(|a| *a != 0) } fn fix(&mut self) { let (q, r) = quot_rem(self.size); if r != 0 { self.a[q] &= (1 << r) - 1; } } fn clear(&mut self) { let len = self.a.len(); self.a.clear(); self.a.resize(len, 0); } fn truncate(&mut self, len: usize) { if len >= self.size { return; } let w = bit_size(); self.a.truncate((len + w - 1) / w); self.size = len; self.fix(); } fn popcnt(&self) -> usize { self.a.iter().fold(0, |s, a| s + a.count_ones() as usize) } fn shift_left(&self, rhs: usize) -> Self { let (q, r) = quot_rem(rhs); let mut ans = BitSet::new(self.size + rhs); if r == 0 { for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) { *x = *y; } } else { let w = bit_size(); let mut prev = 0; for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) { *x = (*y << r) | (prev >> (w - r)); prev = *y; } *ans.a.last_mut().unwrap() |= prev >> (w - r); } ans.fix(); ans } fn shift_right(&self, rhs: usize) -> Self { if rhs >= self.size { return BitSet::new(1); } let (q, r) = quot_rem(rhs); let mut ans = BitSet::new(self.size - rhs); if r == 0 { for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()) { *x = *y; } } else { let w = bit_size(); let mut prev = 0; for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()).rev() { *x |= (*y >> r) | (prev << (w - r)); prev = *y; } } ans.fix(); ans } fn bitwise_or(&self, rhs: &Self) -> Self { let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)}; let mut a = x.a.clone(); for (a, y) in a.iter_mut().zip(y.a.iter()) { *a |= *y; } BitSet { size: x.size, a: a, } } fn bitwise_and(&self, rhs: &Self) -> Self { let (x, y) = if self.size <= rhs.size {(self, rhs)} else {(rhs, self)}; let mut a = x.a.clone(); for (a, y) in a.iter_mut().zip(y.a.iter()) { *a &= *y; } BitSet { size: x.size, a: a, } } fn bitwise_xor(&self, rhs: &Self) -> Self { let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)}; let mut a = x.a.clone(); for (a, y) in a.iter_mut().zip(y.a.iter()) { *a ^= *y; } BitSet { size: x.size, a: a, } } fn bitwise_or_assign(&mut self, rhs: &Self) { if self.size < rhs.size { self.size = rhs.size; self.a.resize(rhs.a.len(), 0); } for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) { *a |= *b; } } fn bitwise_and_assign(&mut self, rhs: &Self) { if self.size > rhs.size { self.size = rhs.size; self.a.resize(rhs.a.len(), 0); } for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) { *a &= *b; } } fn bitwise_xor_assign(&mut self, rhs: &Self) { if self.size < rhs.size { self.size = rhs.size; self.a.resize(rhs.a.len(), 0); } for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) { *a ^= *b; } } fn trailing_zeros(&self) -> usize { let mut ans = 0; for a in self.a.iter() { if *a != 0 { ans += a.trailing_zeros() as usize; break; } else { ans += bit_size(); } } ans } } // ---------- end BitSet ---------- //https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // fn run() { input! { n: usize, m: usize, board: [[chars; n]; m], } let len = n * n; let mut board: Vec = board.into_iter().map(|b| { let mut bit = BitSet::new(len); for (i, b) in b.into_iter().enumerate() { for (j, c) in b.into_iter().enumerate() { if c == '#' { bit.set_at(i * n + j); } } } bit }).collect(); let mut base = vec![]; for i in 0..n { let mut bit = BitSet::new(len); for j in 0..n { bit.set_at(i * n + j); } base.push(bit); } for j in 0..n { let mut bit = BitSet::new(len); for i in 0..n { bit.set_at(i * n + j); } base.push(bit); } for k in 0..(2 * n - 1) { let mut bit = BitSet::new(len); for i in 0..=k { let j = k - i; if i < n && j < n { bit.set_at(i * n + j); } } base.push(bit); } for k in 0..(2 * n - 1) { let mut bit = BitSet::new(len); let mut x = n; let mut y = k + 1; while x > 0 && y > 0 { x -= 1; y -= 1; if x < n && y < n { bit.set_at(x * n + y); } } base.push(bit); } let mut b = base; let mut base = vec![]; while b.len() > 0 { let k = b.iter().map(|b| b.trailing_zeros()).enumerate().min_by_key(|p| p.1).unwrap().0; let v = b.remove(k); let k = v.trailing_zeros(); if k >= len { break; } for b in b.iter_mut() { if b.trailing_zeros() == k { b.bitwise_xor_assign(&v); } } base.push(v); } for a in board.iter_mut() { for b in base.iter() { let k = b.trailing_zeros(); if a.get_at(k) { a.bitwise_xor_assign(b); } } } let mut ans = String::new(); for i in 0..(m - 1) { for j in (i + 1)..m { if board[i] == board[j] { ans.push('1'); } else { ans.push('0'); } } ans.push('\n'); } print!("{}", ans); } fn main() { run(); }