結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー akakimidoriakakimidori
提出日時 2022-04-12 23:48:26
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 2,982 ms / 4,000 ms
コード長 3,814 bytes
コンパイル時間 14,539 ms
コンパイル使用メモリ 387,092 KB
実行使用メモリ 21,120 KB
最終ジャッジ日時 2024-06-10 18:14:32
合計ジャッジ時間 27,212 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2,982 ms
21,120 KB
testcase_08 AC 2,956 ms
21,120 KB
testcase_09 AC 2,980 ms
21,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::ops::*;

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

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

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 {
        use core::arch::x86_64::*;
        unsafe {
            let a = _mm_set_epi64x(0, self.0 as i64);
            let b = _mm_set_epi64x(0, rhs.0 as i64);
            let c = _mm_clmulepi64_si128(a, b, 0);
            Value(_mm_extract_epi64(c, 0) as usize)
        }
    }
}
// ---------- 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::zero(); 1 << n];
    let mut b = vec![Value::zero(); 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;
        }
    }
    let mut c = vec![Value::zero(); 1 << n];
    rec(&mut c, &mut a, &mut 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);
}

fn rec(c: &mut [Value], a: &mut [Value], b: &mut [Value]) {
    if c.len() <= 32 {
        for (i, a) in a.iter().enumerate() {
            for (j, b) in b.iter().enumerate() {
                c[i ^ j] = c[i ^ j] + *a * *b;
            }
        }
        return;
    }
    let m = c.len() / 2;
    let (al, ar) = a.split_at_mut(m);
    let (bl, br) = b.split_at_mut(m);
    let (cl, cr) = c.split_at_mut(m);
    rec(cl, al, bl);
    rec(cr, ar, br);
    let it = cl.iter_mut().zip(cr.iter_mut());
    let it = it.zip(al.iter_mut().zip(ar.iter_mut()));
    let it = it.zip(bl.iter_mut().zip(br.iter_mut()));
    for (((cl, cr), (al, ar)), (bl, br)) in it {
        *cl = *cl + *cr;
        *cr = Value::zero();
        *al = *al + *ar;
        *bl = *bl + *br;
    }
    rec(cr, al, bl);
    let it = cl.iter_mut().zip(cr.iter_mut());
    let it = it.zip(al.iter_mut().zip(ar.iter_mut()));
    let it = it.zip(bl.iter_mut().zip(br.iter_mut()));
    for (((cl, cr), (al, ar)), (bl, br)) in it {
        *cr = *cr - *cl;
        *al = *al - *ar;
        *bl = *bl - *br;
    }
}
0