Submit Info #9210

Problem Lang User Status Time Memory
Hafnian of Matrix rust noshi91 AC 2917 ms 1.18 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
large_00 AC 26 ms 0.80 MiB
large_01 AC 61 ms 0.88 MiB
large_02 AC 279 ms 0.99 MiB
max_00 AC 2917 ms 1.16 MiB
max_01 AC 2912 ms 1.17 MiB
max_02 AC 2907 ms 1.18 MiB
small_00 AC 1 ms 0.68 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 1 ms 0.72 MiB

use std::io::{self, Read as _, Write as _}; struct Scanner<'a>(std::str::SplitWhitespace<'a>); impl<'a> Scanner<'a> { fn new(s: &'a str) -> Self { Self(s.split_whitespace()) } fn next<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let s = self.0.next().expect("found EOF"); match s.parse() { Ok(v) => v, Err(msg) => { println!( "parse error. T = {}, s = \"{}\": {:?}", std::any::type_name::<T>(), s, msg ); panic!() } } } } mod fp { use std::convert::From; use std::iter; use std::ops; const P: u32 = 998244353; #[derive(Copy, Clone, Debug, Eq, PartialEq)] pub struct Fp(pub u32); impl Fp { pub fn pow(mut self, mut exp: u32) -> Fp { let mut res = Fp(1); while exp != 0 { if exp % 2 != 0 { res *= self; } self *= self; exp /= 2; } res } } macro_rules! impl_from_int { ($(($ty:ty: $via:ty)),*) => { $( impl From<$ty> for Fp { fn from(x: $ty) -> Fp { Fp((x as $via).rem_euclid(P as $via) as u32) } } )* }; } impl_from_int!( (i8: i32), (i16: i32), (i32: i32), (i64: i64), (u8: u32), (u16: u32), (u32: u32), (u64: u64), (isize: i64), (usize: u64) ); impl iter::Product for Fp { fn product<I>(iter: I) -> Fp where I: Iterator<Item = Fp>, { iter.fold(Fp(1), |b, i| b * i) } } impl iter::Sum for Fp { fn sum<I>(iter: I) -> Fp where I: Iterator<Item = Fp>, { iter.fold(Fp(0), |b, i| b + i) } } impl ops::Add<Fp> for Fp { type Output = Fp; fn add(mut self, rhs: Fp) -> Fp { self += rhs; self } } impl ops::AddAssign<Fp> for Fp { fn add_assign(&mut self, rhs: Fp) { self.0 += rhs.0; if self.0 >= P { self.0 -= P; } } } impl ops::Div for Fp { type Output = Fp; fn div(mut self, rhs: Fp) -> Fp { assert_ne!(rhs.0, 0); self /= rhs; self } } impl ops::DivAssign for Fp { fn div_assign(&mut self, rhs: Fp) { assert_ne!(rhs.0, 0); *self *= rhs.pow(P - 2); } } impl ops::Mul<Fp> for Fp { type Output = Fp; fn mul(self, rhs: Fp) -> Fp { Fp((self.0 as u64 * rhs.0 as u64 % P as u64) as u32) } } impl ops::MulAssign<Fp> for Fp { fn mul_assign(&mut self, rhs: Fp) { *self = *self * rhs; } } impl ops::Neg for Fp { type Output = Fp; fn neg(self) -> Fp { Fp(match self.0 { 0 => 0, s => P - s, }) } } impl ops::Sub<Fp> for Fp { type Output = Fp; fn sub(mut self, rhs: Fp) -> Fp { self -= rhs; self } } impl ops::SubAssign<Fp> for Fp { fn sub_assign(&mut self, rhs: Fp) { if self.0 < rhs.0 { self.0 += P; } self.0 -= rhs.0; } } } use fp::Fp; mod hafnian { use super::Fp; pub fn hafnian(a: &Vec<Vec<Fp>>) -> Fp { assert_eq!(a.len() % 2, 0); HafnianFn { n: a.len() / 2 }.solve(a) } struct HafnianFn { n: usize, } impl HafnianFn { fn solve(&self, a: &Vec<Vec<Fp>>) -> Fp { self.f((0..self.n * 2) .map(|i| (0..i).map(|j| self.constant(a[i][j])).collect()) .collect())[self.n] } fn f(&self, mut b: Vec<Vec<Poly>>) -> Poly { if b.is_empty() { return self.constant(Fp(1)); } let x = b.pop().unwrap(); let y = b.pop().unwrap(); let mut ret = self.constant(Fp(0)); { let zero = self.f(b.clone()); for i in 0..=self.n { ret[i] -= zero[i]; } } for (b, x) in b.iter_mut().zip(&x) { for (b, y) in b.iter_mut().zip(&y) { self.aa_mul_shl(b, x, y); } } for (b, y) in b.iter_mut().zip(&y) { for (b, x) in b.iter_mut().zip(&x) { self.aa_mul_shl(b, x, y); } } { let all = self.f(b); self.aa_mul_shl(&mut ret, x.last().unwrap(), &all); for i in 0..=self.n { ret[i] += all[i]; } } ret } fn constant(&self, a: Fp) -> Poly { let mut ret = vec![Fp(0); self.n + 1]; ret[0] = a; ret } fn aa_mul_shl(&self, c: &mut Poly, a: &Poly, b: &Poly) { for i in 0..=self.n { for j in i..=self.n - 1 { c[j + 1] += a[i] * b[j - i]; } } } } type Poly = Vec<Fp>; } fn main() { let mut stdin = String::new(); std::io::stdin().read_to_string(&mut stdin).unwrap(); let mut sc = Scanner::new(&stdin); let stdout = io::stdout(); let mut stdout = io::BufWriter::new(stdout.lock()); let n: usize = sc.next(); let a = (0..n) .map(|_| (0..n).map(|_| Fp(sc.next())).collect()) .collect(); writeln!(stdout, "{}", hafnian::hafnian(&a).0).unwrap(); stdout.flush().unwrap(); }