#482602 (Rust) No.1056 2D Lamps

• 問題: No.1056 2D Lamps
• ユーザー: akakimidori
• 提出日時: 2020-05-16 09:17:01
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 542 ms / 3,000 ms
• コード長: 13,259 bytes
• コンパイル時間: 1,981 ms
• コンパイル使用メモリ: 195,700 KB
• 実行使用メモリ: 43,348 KB
• 最終ジャッジ日時: 2023-10-21 20:47:33
• 合計ジャッジ時間: 9,837 ms
• ジャッジサーバーID （参考情報）: judge14 / judge9

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	1 ms; 4,348 KB
testcase_03	AC	534 ms; 43,348 KB
testcase_04	AC	532 ms; 43,348 KB
testcase_05	AC	532 ms; 43,348 KB
testcase_06	AC	535 ms; 43,348 KB
testcase_07	AC	536 ms; 43,348 KB
testcase_08	AC	533 ms; 43,348 KB
testcase_09	AC	451 ms; 43,348 KB
testcase_10	AC	473 ms; 43,348 KB
testcase_11	AC	532 ms; 43,348 KB
testcase_12	AC	542 ms; 43,348 KB
testcase_13	AC	1 ms; 4,348 KB
testcase_14	AC	1 ms; 4,348 KB
testcase_15	AC	2 ms; 4,348 KB
testcase_16	AC	1 ms; 4,348 KB

ソースコード

// ---------- begin mod vector ----------
#[allow(dead_code)]
mod mod_vector {
    const MOD: u64 = (1u64 << 61) - 1;

    #[derive(Clone, Copy, PartialEq, Eq)]
    struct ModInt(u64);

    impl std::ops::Add for ModInt {
        type Output = Self;
        fn add(self, rhs: Self) -> Self::Output {
            assert!(self.0 < MOD && rhs.0 < MOD);
            let mut d = self.0 + rhs.0;
            if d >= MOD {
                d -= MOD;
            }
            ModInt(d)
        }
    }

    impl std::ops::Sub for ModInt {
        type Output = Self;
        fn sub(self, rhs: Self) -> Self::Output {
            assert!(self.0 < MOD && rhs.0 < MOD);
            let mut d = self.0 + MOD - rhs.0;
            if d >= MOD {
                d -= MOD;
            }
            ModInt(d)
        }
    }

    impl std::ops::Mul for ModInt {
        type Output = Self;
        fn mul(self, rhs: Self) -> Self::Output {
            assert!(self.0 < MOD && rhs.0 < MOD);
            const MASK31: u64 = (1u64 << 31) - 1;
            const MASK30: u64 = (1u64 << 30) - 1;
            let au = self.0 >> 31;
            let ad = self.0 & MASK31;
            let bu = rhs.0 >> 31;
            let bd = rhs.0 & MASK31;
            let mid = ad * bu + au * bd;
            let midu = mid >> 30;
            let midd = mid & MASK30;
            let sum = au * bu * 2 + midu + (midd << 31) + ad * bd;
            let mut ans = (sum >> 61) + (sum & MOD);
            if ans >= MOD {
                ans -= MOD;
            }
            ModInt(ans)
        }
    }

    impl ModInt {
        fn new(v: u64) -> Self {
            ModInt(v % MOD)
        }
        fn zero() -> Self {
            ModInt(0)
        }
        fn pow(&self, n: u64) -> Self {
            let mut t = ModInt(1);
            let mut s = *self;
            let mut n = n;
            while n > 0 {
                if n & 1 == 1 {
                    t = t * s;
                }
                s = s * s;
                n >>= 1;
            }
            t
        }
        fn inv(&self) -> Self {
            assert!(self.0 > 0);
            self.pow(MOD - 2)
        }
    }

    pub const BASE_NUM: usize = 2;

    #[derive(Clone, PartialEq, Eq)]
    pub struct ModVector {
        val: [ModInt; BASE_NUM],
    }

    impl ModVector {
        pub fn zero() -> Self {
            ModVector {
                val: [ModInt::zero(); BASE_NUM],
            }
        }
        pub fn new(v: &[u64]) -> Self {
            assert!(v.len() >= BASE_NUM);
            let mut ans = ModVector::zero();
            for (x, a) in ans.val.iter_mut().zip(v.iter()) {
                *x = ModInt::new(*a);
            }
            ans
        }
        pub fn one(v: u64) -> Self {
            ModVector::new(&[v; BASE_NUM])
        }
        pub fn add(&self, rhs: &Self) -> Self {
            let mut ans = ModVector::zero();
            for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {
                *c = *a + *b;
            }
            ans
        }
        pub fn sub(&self, rhs: &Self) -> Self {
            let mut ans = ModVector::zero();
            for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {
                *c = *a - *b;
            }
            ans
        }
        pub fn mul(&self, rhs: &Self) -> Self {
            let mut ans = ModVector::zero();
            for (c, (a, b)) in ans.val.iter_mut().zip(self.val.iter().zip(rhs.val.iter())) {
                *c = *a * *b;
            }
            ans
        }
        pub fn inv(&self) -> Self {
            let mut ans = ModVector::zero();
            for (x, a) in ans.val.iter_mut().zip(self.val.iter()) {
                *x = a.inv();
            }
            ans
        }
    }

    pub fn rand_time() -> u32 {
        use std::time::{SystemTime, UNIX_EPOCH};
        SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .unwrap()
            .subsec_nanos()
    }

    pub fn rand_memory() -> u32 {
        Box::into_raw(Box::new("I hope this is a random number")) as u32
    }

    pub fn generate_random_rad() -> ModVector {
        let mut rad = ModVector::zero();
        for (i, v) in rad.val.iter_mut().enumerate() {
            *v = ModInt::new(if i & 1 == 0 {
                rand_time() as u64 + 2
            } else {
                rand_memory() as u64 + 2
            });
        }
        rad
    }
}
// ---------- end mod vector ----------
// ---------- begin BitSet ----------
#[derive(Clone, Eq, PartialEq)]
struct BitSet {
    size: usize,
    a: Vec<usize>,
}

fn bit_size() -> usize {
    8 * std::mem::size_of::<usize>()
}

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::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($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<BitSet> = 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);
    }
    use mod_vector::*;
    let rad = generate_random_rad();
    let mut p = vec![];
    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 q = ModVector::zero();
        for i in 0..len {
            q = q.mul(&rad).add(&ModVector::one(a.get_at(i) as u64 + 3));
        }
        p.push(q);
    }
    let mut ans = String::new();
    for i in 0..(m - 1) {
        for j in (i + 1)..m {
            if p[i] == p[j] {
                ans.push('1');
            } else {
                ans.push('0');
            }
        }
        ans.push('\n');
    }
    print!("{}", ans);
}

fn main() {
    run();
}