Submission #61501928

---

Source Code Expand

use proconio::{input, marker::Bytes};

fn main() {
    input! {n: usize}
    let mut a = vec![];
    for _ in 0..n {
        input! { s: Bytes }
        a.push(data_structure::BitSet::from_bytes(s));
    }
    let mut mask = vec![];
    {
        let mut bytes = vec![b'1'; n];
        for i in 0..n {
            bytes[i] = b'0';
            mask.push(data_structure::BitSet::from_bytes(bytes.clone()));
        }
    }

    let mut ans = 0u64;
    for i in 0..n - 1 {
        for j in i + 1..n {
            if a[i].is_zero_bit(j) {
                continue;
            }
            ans += a[i].and(&a[j]).and(&mask[j]).count() as u64;
        }
    }
    println!("{ans}");
}

#[allow(dead_code)]
mod data_structure {
    use itertools::Itertools;
    use num::PrimInt;

    #[derive(Clone, Debug)]
    pub struct BitSet {
        internal: Vec<u128>,
    }

    impl BitSet {
        pub fn new(length: usize) -> Self {
            Self {
                internal: vec![0; length],
            }
        }

        pub fn from_integer<T: PrimInt>(x: T) -> Self {
            assert!(x >= T::zero());
            Self {
                internal: vec![x.to_u128().unwrap()],
            }
        }

        pub fn from_string(s: String) -> Self {
            assert!(is_01string(&s));
            let n = s.len();
            let mut internal = vec![];
            for i in (0..n).step_by(128) {
                let si = &s[i..i + 128];
                internal.push(u128::from_str_radix(si, 2).unwrap());
            }
            Self { internal }
        }

        /// bytes から生成
        /// bytes の i 番目の要素は下から i ビット目になる
        pub fn from_bytes(bytes: Vec<u8>) -> Self {
            assert!(is_01bytes(&bytes));
            let n = bytes.len();
            let mut internal = vec![];
            for i in (0..n).step_by(128) {
                let string = bytes[i..(i + 128).min(n)]
                    .iter()
                    .rev()
                    .map(|&byte| byte - b'0')
                    .join("");
                internal.push(u128::from_str_radix(&string, 2).unwrap());
            }
            Self { internal }
        }

        pub fn assign(&mut self, i: usize, b: u128) {
            self.extend(i);
            let (i, j) = get_pos_and_bit(i);
            if b == 1 {
                self.internal[i] |= 1 << j;
            } else {
                let mask = u128::MAX - (1 << j);
                self.internal[i] &= mask;
            }
        }

        pub fn count(&self) -> usize {
            let mut count = 0;
            for &integer in self.internal.iter() {
                count += integer.count_ones();
            }
            count as usize
        }

        pub fn is_one_bit(&self, i: usize) -> bool {
            assert!(!self.is_out_of_range(i));
            let (i, j) = get_pos_and_bit(i);
            (self.internal[i] >> j & 1) == 1
        }
        pub fn is_zero_bit(&self, i: usize) -> bool {
            !self.is_one_bit(i)
        }
        pub fn is_zero(&self) -> bool {
            self.internal.iter().all(|x| x == &0)
        }

        pub fn and_inplace(&mut self, other: &Self) {
            let n = self.internal.len().min(other.internal.len());
            for i in 0..n {
                self.internal[i] &= other.internal[i];
            }
            while self.internal.len() > n {
                self.internal.pop();
            }
        }
        pub fn and(&self, other: &Self) -> Self {
            let mut and = Self {
                internal: self.internal.clone(),
            };
            and.and_inplace(other);
            and
        }

        pub fn or_inplace(&mut self, other: &Self) {
            let n = self.internal.len().min(other.internal.len());
            for i in 0..n {
                self.internal[i] |= other.internal[i];
            }
            for i in n..other.internal.len() {
                self.internal.push(other.internal[i]);
            }
        }
        pub fn or(&self, other: &Self) -> Self {
            let mut or = Self {
                internal: self.internal.clone(),
            };
            or.or_inplace(other);
            or
        }

        pub fn xor_inplace(&mut self, other: &Self) {
            let n = self.internal.len().min(other.internal.len());
            for i in 0..n {
                self.internal[i] ^= other.internal[i];
            }
            for i in n..other.internal.len() {
                self.internal.push(other.internal[i]);
            }
        }

        pub fn xor(&self, other: &Self) -> Self {
            let mut xor = Self {
                internal: self.internal.clone(),
            };
            xor.xor_inplace(other);
            xor
        }

        pub fn min(&self, other: &Self) -> Self {
            let m = self.internal.len().max(other.internal.len());
            for i in (0..m).rev() {
                let x = if i < self.internal.len() {
                    self.internal[i]
                } else {
                    0
                };
                let y = if i < other.internal.len() {
                    other.internal[i]
                } else {
                    0
                };

                if x == y {
                    continue;
                } else if x < y {
                    return Self {
                        internal: self.internal.clone(),
                    };
                } else {
                    return Self {
                        internal: other.internal.clone(),
                    };
                }
            }
            Self {
                internal: self.internal.clone(),
            }
        }

        fn is_out_of_range(&self, i: usize) -> bool {
            i / 128 >= self.internal.len()
        }
        fn extend(&mut self, i: usize) {
            while self.internal.len() <= i / 128 {
                self.internal.push(0);
            }
        }
    }

    fn is_01string(s: &str) -> bool {
        is_01bytes(s.as_bytes())
    }
    fn is_01bytes(bytes: &[u8]) -> bool {
        bytes.iter().all(|bi| bi == &b'0' || bi == &b'1')
    }
    fn get_pos_and_bit(i: usize) -> (usize, usize) {
        (i / 128, i % 128)
    }
}

Submission Info

Judge Result