結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー akakimidori
提出日時 2022-04-08 19:35:15
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,072 ms / 4,000 ms
コード長 4,803 bytes
コンパイル時間 15,813 ms
コンパイル使用メモリ 378,184 KB
実行使用メモリ 41,856 KB
最終ジャッジ日時 2024-11-08 13:49:05
合計ジャッジ時間 24,728 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// ---------- begin bitwise transform ----------
pub fn bitwise_transform<T, F>(a: &mut [T], mut f: F)
where
    F: FnMut(&mut T, &mut T),
{
    let n = a.len().trailing_zeros() as usize;
    assert!(a.len() == 1 << n);
    for i in 0..n {
        for a in a.chunks_exact_mut(2 << i) {
            let (x, y) = a.split_at_mut(1 << i);
            for (x, y) in x.iter_mut().zip(y) {
                f(x, y);
            }
        }
    }
}
// ---------- end bitwise transform ----------

use std::ops::*;

pub trait SubsetConvValue:
    Copy + Add<Output = Self> + Mul<Output = Self> + Sub<Output = Self>
{
    fn zero() -> Self;
}

fn subset_rec<T: SubsetConvValue>(x: &mut [T], y: &mut [T], n: usize) {
    if x.len() == n + 1 {
        for i in (0..=n).rev() {
            x[i] = x[..=i]
                .iter()
                .zip(y[..=i].iter().rev())
                .fold(T::zero(), |s, p| s + *p.0 * *p.1);
        }
        return;
    }
    let m = x.len() / 2;
    let (a, b) = x.split_at_mut(m);
    let (c, d) = y.split_at_mut(m);
    let x = b.iter_mut().zip(a.iter());
    let y = d.iter_mut().zip(c.iter());
    for ((b, a), (d, c)) in x.zip(y) {
        *b = *b + *a;
        *d = *d + *c;
    }
    subset_rec(a, c, n);
    subset_rec(b, d, n);
    for (b, a) in b.iter_mut().zip(a.iter()) {
        *b = *b - *a;
    }
}

pub fn subset_convolution<T: SubsetConvValue>(a: &[T], b: &[T]) -> Vec<T> {
    let size = a.len().next_power_of_two();
    assert!(a.len() == size && b.len() == size);
    let n = size.trailing_zeros() as usize;
    let mut x = vec![T::zero(); (n + 1) << n];
    let mut y = vec![T::zero(); (n + 1) << n];
    for (x, a) in [(&mut x, &a), (&mut y, &b)].iter_mut() {
        for (i, a) in a.iter().enumerate() {
            x[i * (n + 1) + i.count_ones() as usize] = *a;
        }
    }
    subset_rec(&mut x, &mut y, n);
    let mut res = vec![T::zero(); 1 << n];
    for (i, (res, x)) in res.iter_mut().zip(x.chunks_exact(n + 1)).enumerate() {
        *res = x[i.count_ones() as usize];
    }
    res
}

#[derive(Clone, Copy)]
struct Value(usize);

impl Add for Value {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        Value(self.0 ^ rhs.0)
    }
}

impl Sub for Value {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        Value(self.0 ^ rhs.0)
    }
}

impl Mul for Value {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        let mut res = 0;
        for i in 0..32 {
            if self.0 >> i & 1 == 1 {
                res ^= rhs.0 << i;
            }
        }
        Value(res)
    }
}

impl SubsetConvValue for Value {
    fn zero() -> Self {
        Value(0)
    }
}

// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let n: usize = sc.next(b'\n');
    let mut a = vec![Value(0usize); 1 << n];
    let mut b = vec![Value(0usize); 1 << n];
    for a in a.iter_mut().chain(b.iter_mut()) {
        for i in 0..32 {
            let x = sc.next::<usize>(if i == 31 { b'\n' } else { b' ' });
            a.0 |= x << i;
        }
    }
    bitwise_transform(&mut a, |a, b| *a = *a + *b);
    bitwise_transform(&mut b, |a, b| *a = *a + *b);
    let mut c = subset_convolution(&a, &b);
    bitwise_transform(&mut c, |a, b| *a = *a + *b);
    use std::fmt::*;
    let mut s = String::new();
    for c in c {
        for i in 0..63 {
            let p = c.0 >> i & 1;
            write!(&mut s, "{} ", p).ok();
        }
        s.pop();
        s.push('\n');
    }
    print!("{}", s);
}
0