結果
問題 | No.1210 XOR Grid |
ユーザー | cotton_fn_ |
提出日時 | 2020-12-09 13:23:03 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 16,383 bytes |
コンパイル時間 | 18,773 ms |
コンパイル使用メモリ | 378,828 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 01:07:34 |
合計ジャッジ時間 | 20,342 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 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,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 9 ms
5,376 KB |
testcase_26 | AC | 8 ms
5,376 KB |
testcase_27 | AC | 9 ms
5,376 KB |
testcase_28 | AC | 8 ms
5,376 KB |
testcase_29 | AC | 8 ms
5,376 KB |
testcase_30 | AC | 7 ms
5,376 KB |
testcase_31 | AC | 8 ms
5,376 KB |
testcase_32 | AC | 8 ms
5,376 KB |
testcase_33 | AC | 1 ms
5,376 KB |
testcase_34 | AC | 1 ms
5,376 KB |
testcase_35 | AC | 1 ms
5,376 KB |
testcase_36 | AC | 3 ms
5,376 KB |
testcase_37 | AC | 3 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 5 ms
5,376 KB |
testcase_41 | AC | 5 ms
5,376 KB |
testcase_42 | AC | 15 ms
5,376 KB |
testcase_43 | AC | 14 ms
5,376 KB |
testcase_44 | AC | 15 ms
5,376 KB |
testcase_45 | AC | 15 ms
5,376 KB |
testcase_46 | AC | 14 ms
5,376 KB |
testcase_47 | AC | 5 ms
5,376 KB |
testcase_48 | AC | 5 ms
5,376 KB |
testcase_49 | AC | 1 ms
5,376 KB |
testcase_50 | AC | 8 ms
5,376 KB |
testcase_51 | AC | 15 ms
5,376 KB |
testcase_52 | AC | 14 ms
5,376 KB |
testcase_53 | AC | 15 ms
5,376 KB |
testcase_54 | AC | 5 ms
5,376 KB |
testcase_55 | AC | 10 ms
5,376 KB |
testcase_56 | AC | 8 ms
5,376 KB |
testcase_57 | AC | 8 ms
5,376 KB |
testcase_58 | AC | 1 ms
5,376 KB |
testcase_59 | AC | 1 ms
5,376 KB |
ソースコード
#![allow(unused_imports, unused_macros)] use kyoproio::*; use std::{ collections::*, io::{self, prelude::*}, iter, mem::{replace, swap}, }; fn run<I: Input, O: Write>(mut kin: I, out: O) { let mut out = KOutput::new(out); let (n, m, x): (usize, usize, u64) = kin.input(); let s = kin.iter::<u64>().take(n + m).fold(0, |x, y| x ^ y); if s != 0 { outln!(out, 0); } else { let ans = mint(2).pow(n - 1).pow(m - 1).pow(x); outln!(out, ans.get()); } } use std::{cmp, fmt, marker::PhantomData, ops}; pub type Mint = ModInt<Mod1e9p7>; pub fn mint(x: u32) -> Mint { ModInt::new(x) } pub trait Modulo { fn modulo() -> u32; } macro_rules! modulo_impl { ($($Type:ident $val:tt)*) => { $(pub struct $Type; impl Modulo for $Type { fn modulo() -> u32 { $val } })* }; } modulo_impl!(Mod998244353 998244353 Mod1e9p7 1000000007); use std::sync::atomic; pub struct VarMod; static VAR_MOD: atomic::AtomicU32 = atomic::AtomicU32::new(0); pub fn set_var_mod(m: u32) { VAR_MOD.store(m, atomic::Ordering::Relaxed); } impl Modulo for VarMod { fn modulo() -> u32 { VAR_MOD.load(atomic::Ordering::Relaxed) } } pub struct ModInt<M>(u32, PhantomData<M>); impl<M: Modulo> ModInt<M> { pub fn new(x: u32) -> Self { debug_assert!(x < M::modulo()); Self(x, PhantomData) } pub fn normalize(self) -> Self { if self.0 < M::modulo() { self } else { Self::new(self.0 % M::modulo()) } } pub fn get(self) -> u32 { self.0 } pub fn inv(self) -> Self { self.pow(M::modulo() - 2) } pub fn half(self) -> Self { Self::new(self.0 / 2 + self.0 % 2 * ((M::modulo() + 1) / 2)) } pub fn modulo() -> u32 { M::modulo() } } impl<M: Modulo> ops::Neg for ModInt<M> { type Output = Self; fn neg(self) -> Self { Self::new(if self.0 == 0 { 0 } else { M::modulo() - self.0 }) } } impl<M: Modulo> ops::Add for ModInt<M> { type Output = Self; fn add(self, rhs: Self) -> Self { let s = self.0 + rhs.0; Self::new(if s < M::modulo() { s } else { s - M::modulo() }) } } impl<M: Modulo> ops::Sub for ModInt<M> { type Output = Self; fn sub(self, rhs: Self) -> Self { Self::new(if self.0 >= rhs.0 { self.0 - rhs.0 } else { M::modulo() + self.0 - rhs.0 }) } } impl<M: Modulo> ops::Mul for ModInt<M> { type Output = Self; fn mul(self, rhs: Self) -> Self { Self::new((self.0 as u64 * rhs.0 as u64 % M::modulo() as u64) as u32) } } impl<M: Modulo> ops::Div for ModInt<M> { type Output = Self; fn div(self, rhs: Self) -> Self { assert_ne!(rhs.get(), 0); self * rhs.inv() } } macro_rules! op_impl { ($($Op:ident $op:ident $OpAssign:ident $op_assign:ident)*) => { $(impl<M: Modulo> ops::$Op<&Self> for ModInt<M> { type Output = Self; fn $op(self, rhs: &Self) -> Self { self.$op(*rhs) } } impl<M: Modulo> ops::$Op<ModInt<M>> for &ModInt<M> { type Output = ModInt<M>; fn $op(self, rhs: ModInt<M>) -> ModInt<M> { (*self).$op(rhs) } } impl<M: Modulo> ops::$Op<&ModInt<M>> for &ModInt<M> { type Output = ModInt<M>; fn $op(self, rhs: &ModInt<M>) -> ModInt<M> { (*self).$op(*rhs) } } impl<M: Modulo> ops::$OpAssign for ModInt<M> { fn $op_assign(&mut self, rhs: Self) { *self = ops::$Op::$op(*self, rhs); } } impl<M: Modulo> ops::$OpAssign<&ModInt<M>> for ModInt<M> { fn $op_assign(&mut self, rhs: &ModInt<M>) { self.$op_assign(*rhs); } })* }; } op_impl! { Add add AddAssign add_assign Sub sub SubAssign sub_assign Mul mul MulAssign mul_assign Div div DivAssign div_assign } impl<M: Modulo> std::iter::Sum for ModInt<M> { fn sum<I: Iterator<Item = Self>>(iter: I) -> Self { iter.fold(ModInt::new(0), |x, y| x + y) } } impl<M: Modulo> std::iter::Product for ModInt<M> { fn product<I: Iterator<Item = Self>>(iter: I) -> Self { iter.fold(ModInt::new(1), |x, y| x * y) } } pub trait Pow<T> { fn pow(self, n: T) -> Self; } impl<M: Modulo> Pow<u32> for ModInt<M> { fn pow(mut self, mut n: u32) -> Self { let mut y = Self::new(1); while n > 0 { if n % 2 == 1 { y *= self; } self *= self; n /= 2; } y } } macro_rules! mod_int_pow_impl { ($($T:ident)*) => { $(impl<M: Modulo> Pow<$T> for ModInt<M> { fn pow(self, n: $T) -> Self { self.pow(n.rem_euclid(M::modulo() as $T - 1) as u32) } })* }; } mod_int_pow_impl!(isize i32 i64 usize u64); macro_rules! mod_int_from_impl { ($($T:ident)*) => { $(impl<M: Modulo> From<$T> for ModInt<M> { #[allow(unused_comparisons)] fn from(x: $T) -> Self { if M::modulo() <= $T::max_value() as u32 { Self::new(x.rem_euclid(M::modulo() as $T) as u32) } else if x < 0 { Self::new((M::modulo() as i32 + x as i32) as u32) } else { Self::new(x as u32) } } })* } } mod_int_from_impl!(isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128); impl<M> Copy for ModInt<M> {} impl<M> Clone for ModInt<M> { fn clone(&self) -> Self { *self } } impl<M: Modulo> Default for ModInt<M> { fn default() -> Self { Self::new(0) } } impl<M> cmp::PartialEq for ModInt<M> { fn eq(&self, other: &Self) -> bool { self.0 == other.0 } } impl<M> cmp::Eq for ModInt<M> {} impl<M> cmp::PartialOrd for ModInt<M> { fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { self.0.partial_cmp(&other.0) } } impl<M> cmp::Ord for ModInt<M> { fn cmp(&self, other: &Self) -> cmp::Ordering { self.0.cmp(&other.0) } } impl<M> std::hash::Hash for ModInt<M> { fn hash<H: std::hash::Hasher>(&self, state: &mut H) { self.0.hash(state); } } impl<M> fmt::Display for ModInt<M> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { self.0.fmt(f) } } impl<M> fmt::Debug for ModInt<M> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.pad("ModInt(")?; self.0.fmt(f)?; f.pad(")") } } // ----------------------------------------------------------------------------- fn main() -> io::Result<()> { std::thread::Builder::new() .stack_size(64 * 1024 * 1024) .spawn(|| { run( KInput::new(io::stdin().lock()), io::BufWriter::new(io::stdout().lock()), ) })? .join() .unwrap(); Ok(()) } // ----------------------------------------------------------------------------- pub mod kyoproio { use std::{ io::prelude::*, iter::FromIterator, marker::PhantomData, mem::{self, MaybeUninit}, ptr, slice, str, }; pub trait Input { fn bytes(&mut self) -> &[u8]; fn str(&mut self) -> &str { str::from_utf8(self.bytes()).unwrap() } fn input<T: InputItem>(&mut self) -> T { T::input(self) } fn iter<T: InputItem>(&mut self) -> Iter<T, Self> { Iter(self, PhantomData) } fn seq<T: InputItem, B: FromIterator<T>>(&mut self, n: usize) -> B { self.iter().take(n).collect() } } pub struct KInput<R> { src: R, buf: Vec<u8>, pos: usize, len: usize, } impl<R: Read> KInput<R> { pub fn new(src: R) -> Self { Self { src, buf: vec![0; 1 << 16], pos: 0, len: 0, } } fn read(&mut self) -> usize { if self.pos > 0 { self.buf.copy_within(self.pos..self.len, 0); self.len -= self.pos; self.pos = 0; } else if self.len >= self.buf.len() { self.buf.resize(2 * self.buf.len(), 0); } let n = self.src.read(&mut self.buf[self.len..]).unwrap(); self.len += n; n } } impl<R: Read> Input for KInput<R> { fn bytes(&mut self) -> &[u8] { loop { while let Some(d) = self.buf[self.pos..self.len] .iter() .position(u8::is_ascii_whitespace) { let p = self.pos; self.pos += d + 1; if d > 0 { return &self.buf[p..p + d]; } } if self.read() == 0 { return &self.buf[mem::replace(&mut self.pos, self.len)..self.len]; } } } } pub struct Iter<'a, T, I: ?Sized>(&'a mut I, PhantomData<*const T>); impl<'a, T: InputItem, I: Input + ?Sized> Iterator for Iter<'a, T, I> { type Item = T; fn next(&mut self) -> Option<T> { Some(self.0.input()) } fn size_hint(&self) -> (usize, Option<usize>) { (!0, None) } } pub trait InputItem: Sized { fn input<I: Input + ?Sized>(src: &mut I) -> Self; } impl InputItem for Vec<u8> { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.bytes().to_owned() } } macro_rules! from_str { ($($T:ty)*) => { $(impl InputItem for $T { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.str().parse::<$T>().unwrap() } })* } } from_str!(String char bool f32 f64); macro_rules! parse_int { ($($I:ty: $U:ty)*) => { $(impl InputItem for $I { fn input<I: Input + ?Sized>(src: &mut I) -> Self { let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I); let s = src.bytes(); if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) } } } impl InputItem for $U { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U) } })* }; } parse_int!(isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128); macro_rules! tuple { ($H:ident $($T:ident)*) => { impl<$H: InputItem, $($T: InputItem),*> InputItem for ($H, $($T),*) { fn input<I: Input + ?Sized>(src: &mut I) -> Self { ($H::input(src), $($T::input(src)),*) } } tuple!($($T)*); }; () => {} } tuple!(A B C D E F G); macro_rules! array { ($($N:literal)*) => { $(impl<T: InputItem> InputItem for [T; $N] { fn input<I: Input + ?Sized>(src: &mut I) -> Self { let mut arr = MaybeUninit::uninit(); let ptr = arr.as_mut_ptr() as *mut T; unsafe { for i in 0..$N { ptr.add(i).write(src.input()); } arr.assume_init() } } })* }; } array!(1 2 3 4 5 6 7 8); pub struct KOutput<W: Write> { dest: W, delim: bool, } impl<W: Write> KOutput<W> { pub fn new(dest: W) -> Self { Self { dest, delim: false } } pub fn bytes(&mut self, s: &[u8]) { self.dest.write_all(s).unwrap(); } pub fn byte(&mut self, b: u8) { self.bytes(slice::from_ref(&b)); } pub fn output<T: OutputItem>(&mut self, x: T) { if self.delim { self.byte(b' '); } self.delim = true; x.output(self); } pub fn ln(&mut self) { self.delim = false; self.byte(b'\n'); self.flush_debug(); } pub fn inner(&mut self) -> &mut W { &mut self.dest } pub fn seq<T: OutputItem, I: IntoIterator<Item = T>>(&mut self, iter: I) { for x in iter.into_iter() { self.output(x); } } pub fn flush(&mut self) { self.dest.flush().unwrap(); } pub fn flush_debug(&mut self) { if cfg!(debug_assertions) { self.flush(); } } } pub trait OutputItem { fn output<W: Write>(self, dest: &mut KOutput<W>); } impl OutputItem for &str { fn output<W: Write>(self, dest: &mut KOutput<W>) { dest.bytes(self.as_bytes()); } } impl OutputItem for char { fn output<W: Write>(self, dest: &mut KOutput<W>) { self.encode_utf8(&mut [0; 4]).output(dest); } } macro_rules! output_fmt { ($($T:ty)*) => { $(impl OutputItem for $T { fn output<W: Write>(self, dest: &mut KOutput<W>) { write!(dest.inner(), "{}", self).unwrap(); } })* } } output_fmt!(f32 f64); macro_rules! output_int { ($conv:ident; $U:ty; $($T:ty)*) => { $(impl OutputItem for $T { fn output<W: Write>(self, dest: &mut KOutput<W>) { let mut buf = MaybeUninit::<[u8; 20]>::uninit(); unsafe { let ptr = buf.as_mut_ptr() as *mut u8; let ofs = $conv(self as $U, ptr, 20); dest.bytes(slice::from_raw_parts(ptr.add(ofs), 20 - ofs)); } } } impl OutputItem for &$T { fn output<W: Write>(self, dest: &mut KOutput<W>) { (*self).output(dest); } })* }; } output_int!(i64_to_bytes; i64; isize i8 i16 i32 i64); output_int!(u64_to_bytes; u64; usize u8 u16 u32 u64); static DIGITS_LUT: &[u8; 200] = b"0001020304050607080910111213141516171819\ 2021222324252627282930313233343536373839\ 4041424344454647484950515253545556575859\ 6061626364656667686970717273747576777879\ 8081828384858687888990919293949596979899"; unsafe fn i64_to_bytes(x: i64, buf: *mut u8, len: usize) -> usize { let (neg, x) = if x < 0 { (true, -x) } else { (false, x) }; let mut i = u64_to_bytes(x as u64, buf, len); if neg { i -= 1; *buf.add(i) = b'-'; } i } unsafe fn u64_to_bytes(mut x: u64, buf: *mut u8, len: usize) -> usize { let lut = DIGITS_LUT.as_ptr(); let mut i = len; let mut two = |x| { i -= 2; ptr::copy_nonoverlapping(lut.add(2 * x), buf.add(i), 2); }; while x >= 10000 { let rem = (x % 10000) as usize; two(rem % 100); two(rem / 100); x /= 10000; } let mut x = x as usize; if x >= 100 { two(x % 100); x /= 100; } if x >= 10 { two(x); } else { i -= 1; *buf.add(i) = x as u8 + b'0'; } i } #[macro_export] macro_rules! out { ($out:expr, $($args:expr),*) => {{ $($out.output($args);)* }}; } #[macro_export] macro_rules! outln { ($out:expr) => { $out.ln(); }; ($out:expr, $($args:expr),*) => {{ out!($out, $($args),*); outln!($out); }} } #[macro_export] macro_rules! kdbg { ($($v:expr),*) => { if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) } } } }