結果
問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│ |
ユーザー | へのく |
提出日時 | 2021-06-16 20:09:40 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 64 ms / 5,000 ms |
コード長 | 43,535 bytes |
コンパイル時間 | 15,399 ms |
コンパイル使用メモリ | 384,292 KB |
実行使用メモリ | 23,708 KB |
最終ジャッジ日時 | 2024-06-10 00:52:01 |
合計ジャッジ時間 | 13,971 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 0 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 0 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 0 ms
6,944 KB |
testcase_15 | AC | 5 ms
6,940 KB |
testcase_16 | AC | 15 ms
6,940 KB |
testcase_17 | AC | 31 ms
12,296 KB |
testcase_18 | AC | 40 ms
15,548 KB |
testcase_19 | AC | 31 ms
12,332 KB |
testcase_20 | AC | 52 ms
19,528 KB |
testcase_21 | AC | 21 ms
8,772 KB |
testcase_22 | AC | 45 ms
17,808 KB |
testcase_23 | AC | 15 ms
6,944 KB |
testcase_24 | AC | 49 ms
18,180 KB |
testcase_25 | AC | 55 ms
21,440 KB |
testcase_26 | AC | 64 ms
23,708 KB |
コンパイルメッセージ
warning: unused imports: `Fps`, `independent::integer::Int` --> src/main.rs:377:52 | 377 | formal_power_series::{Convolution, Fps}, | ^^^ 378 | }, 379 | independent::integer::Int, | ^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
#![allow(non_snake_case)] use crate::{combinations::array::Comb, scanner::Scanner}; modint!(); fn main() { let mut scan = Scanner::new(); let x = scan.int(); let y = scan.int(); let z = scan.int(); if x == 0 && y == 0 && z == 0 { println!("1"); return; } let n = x + y + z + 1; let comb = Comb::new(n + x.max(y).max(z)); let mut h = fps_anymod![Z::new(0);x+y+z+2]; for i in 0..=x + y + z + 1 { if (n - i) % 2 == 0 { h[i] = comb.of(n, i); } else { h[i] = Z::new(0) - comb.of(n, i); } } h -= Z::new(1); h.div_sps(&list![(0, Z::new(-2)), (1, Z::new(1))]); let mut ret = Z::new(0); for i in 0..=x + y + z + 1 { ret += h[i] * comb.rep(i, x) * comb.rep(i, y) * comb.rep(i, z); } println!("{}", ret); } pub mod combinations { pub mod array { use crate::{arraylist::List, modulo::ModInt}; pub struct Comb<T: ModInt> { fact: List<T>, ifact: List<T>, } impl<T: ModInt> Comb<T> { pub fn new(n: isize) -> Self { let mut fact = List::init(T::zero(), n + 1); let mut ifact = List::init(T::zero(), n + 1); fact[0] = T::one(); for i in 1..=n { fact[i] = fact[i - 1] * T::from_isize(i); } ifact[n] = fact[n].inv(); for i in (1..=n).rev() { ifact[i - 1] = ifact[i] * T::from_isize(i); } Comb { fact, ifact } } pub fn of(&self, n: isize, k: isize) -> T { if n < k || n < 0 || k < 0 { T::zero() } else { self.fact[n] * self.ifact[k] * self.ifact[n - k] } } pub fn rep(&self, n: isize, k: isize) -> T { self.of(n + k - 1, k) } } } } pub mod fps { pub mod formal_power_series { use std::{ fmt::Debug, iter::FromIterator, marker::PhantomData, ops::{ Add, AddAssign, Div, DivAssign, Index, IndexMut, Mul, MulAssign, Neg, Rem, RemAssign, Shl, Shr, Sub, SubAssign, }, }; use crate::{ arraylist::{lst, List}, assign_simple, independent::integer::Int, list, modulo::ModInt, }; pub trait Convolution<T> { fn convolution(a: &[T], b: &[T]) -> List<T>; } impl<T: Int, F: Convolution<T>> From<&lst<T>> for Fps<T, F> { fn from(lst: &lst<T>) -> Self { Self::new(lst.list()) } } impl<T: Int, F: Convolution<T>> FromIterator<T> for Fps<T, F> { fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self { Self::new(iter.into_iter().collect()) } } #[derive(PartialEq, Eq)] pub struct Fps<T, F: Convolution<T>> { pub data: List<T>, phantom: PhantomData<fn() -> F>, } impl<T: Int, F: Convolution<T>> Clone for Fps<T, F> { fn clone(&self) -> Self { Self::new(self.data.clone()) } } impl<T: Int + Debug, F: Convolution<T>> Debug for Fps<T, F> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { self.data.fmt(f) } } impl<T: Int, F: Convolution<T>> Fps<T, F> { pub fn new(data: List<T>) -> Fps<T, F> { Fps { data, phantom: PhantomData, } } pub fn empty() -> Self { Self::new(List::new()) } pub fn lens(&self) -> isize { self.data.lens() } pub fn is_empty(&self) -> bool { self.data.lens() == 0 } pub fn resize(&mut self, new_len: isize) { self.data.resize(new_len, T::zero()); } pub fn shrink(&mut self) { while self.data.last() == Some(&T::zero()) { self.data.pop(); } } pub fn pre(&self, size: isize) -> Self { Self::from(&self.data[..self.lens().min(size)]) } pub fn inv(&self, deg: impl Into<Option<isize>>) -> Self where T: ModInt, { assert!(self[0] != T::zero()); let n = self.lens(); let deg = deg.into().unwrap_or(n); let mut ret = Self::new(list![T::one() / self[0]]); let mut i = 1; while i < deg { ret = (&ret + &ret - &ret * &ret * &self.pre(i << 1)).pre(i << 1); i <<= 1; } ret.pre(deg) } pub fn div_sps(&mut self, g: &lst<(isize, T)>) { let n = self.lens(); assert!(g.lens() >= 1); let &(d, c) = g.first_exn(); assert!(c != T::zero() && d == 0); let ic = T::one() / c; for i in 0..n { for &(j, b) in &g[1..] { if j > i { break; } assign_simple![(self[i]) -= self[i - j] * b]; } self[i] *= ic; } } } macro_rules! impl_ops { (@T $guard:ident, $tpe:ident, $fname:ident, $op: tt) => { impl<T: $guard, F: Convolution<T>> $tpe<T> for &Fps<T, F> { type Output = Fps<T, F>; fn $fname(self, rhs: T) -> Self::Output { let mut ret: Fps<T, F> = self.clone(); ret $op rhs; ret } } impl<T: $guard, F: Convolution<T>> $tpe<T> for Fps<T, F> { type Output = Fps<T, F>; fn $fname(self, rhs: T) -> Self::Output { let mut ret: Fps<T, F> = self.clone(); ret $op rhs; ret } } impl_ops!($guard, $tpe, $fname, $op); }; ($guard:ident, $tpe:ident, $fname:ident, $op:tt) => { impl<T: $guard, F: Convolution<T>> $tpe<&Self> for Fps<T, F> { type Output = Fps<T, F>; fn $fname(self, rhs: &Self) -> Self::Output { let mut ret: Fps<T, F> = self.clone(); ret $op rhs; ret } } impl<T: $guard, F: Convolution<T>> $tpe for Fps<T, F> { type Output = Fps<T, F>; fn $fname(self, rhs: Self) -> Self::Output { let mut ret: Fps<T, F> = self.clone(); ret $op &rhs; ret } } impl<T: $guard, F: Convolution<T>> $tpe for &Fps<T, F> { type Output = Fps<T, F>; fn $fname(self, rhs: Self) -> Self::Output { let mut ret: Fps<T, F> = self.clone(); ret $op rhs; ret } } }; } impl_ops!(@T Int, Add, add, +=); impl_ops!(@T Int, Sub, sub, -=); impl_ops!(@T Int, Mul, mul, *=); impl_ops!(ModInt, Div, div, /=); impl_ops!(ModInt, Rem, rem, %=); impl<T: Int, F: Convolution<T>> Neg for &Fps<T, F> { type Output = Fps<T, F>; fn neg(self) -> Self::Output { let data = self.data.map(|x| T::zero() - x); Fps { data, phantom: PhantomData, } } } impl<T: Int, F: Convolution<T>> AddAssign<&Self> for Fps<T, F> { fn add_assign(&mut self, rhs: &Self) { if rhs.lens() > self.lens() { self.resize(rhs.lens()) }; self.data .iter_mut() .zip(rhs.data.iter()) .for_each(|(e, r)| *e += *r); } } impl<T: Int, F: Convolution<T>> AddAssign<T> for Fps<T, F> { fn add_assign(&mut self, rhs: T) { if self.is_empty() { self.resize(1) }; self[0] += rhs; } } impl<T: Int, F: Convolution<T>> SubAssign<&Self> for Fps<T, F> { fn sub_assign(&mut self, rhs: &Self) { if rhs.lens() > self.lens() { self.resize(rhs.lens()) }; self.data .iter_mut() .zip(rhs.data.iter()) .for_each(|(e, r)| *e -= *r); self.shrink(); } } impl<T: Int, F: Convolution<T>> SubAssign<T> for Fps<T, F> { fn sub_assign(&mut self, rhs: T) { if self.is_empty() { self.resize(1); } self[0] -= rhs; self.shrink(); } } impl<T: Int, F: Convolution<T>> MulAssign<T> for Fps<T, F> { fn mul_assign(&mut self, rhs: T) { for e in self.data.iter_mut() { *e *= rhs; } } } impl<T: Int, F: Convolution<T>> MulAssign<&Self> for Fps<T, F> { fn mul_assign(&mut self, rhs: &Self) { self.data = F::convolution(&self.data, &rhs.data); } } impl<T: ModInt, F: Convolution<T>> RemAssign<&Self> for Fps<T, F> { fn rem_assign(&mut self, rhs: &Self) { *self -= &(&*self / rhs * rhs); } } impl<T: ModInt, F: Convolution<T>> DivAssign<&Self> for Fps<T, F> { fn div_assign(&mut self, rhs: &Self) { let n = self.lens(); self.data = F::convolution(&self.data, &rhs.inv(n).data); self.resize(n); } } impl<T: Int, F: Convolution<T>> Shr<isize> for &Fps<T, F> { type Output = Fps<T, F>; fn shr(self, rhs: isize) -> Self::Output { if self.lens() <= rhs { return Fps::<T, F>::empty(); } Self::Output::from(&self.data[rhs..]) } } impl<T: Int, F: Convolution<T>> Shl<isize> for &Fps<T, F> { type Output = Fps<T, F>; fn shl(self, rhs: isize) -> Self::Output { let mut data = list![T::zero();rhs]; data.append(&self.data); Self::Output::new(data) } } impl<T: Int, F: Convolution<T>> Index<isize> for Fps<T, F> { type Output = T; fn index(&self, index: isize) -> &T { &self.data[index] } } impl<T: Int, F: Convolution<T>> IndexMut<isize> for Fps<T, F> { fn index_mut(&mut self, index: isize) -> &mut T { &mut self.data[index] } } #[macro_export] macro_rules! fps { ([$($args:tt)+] [$($tpe:tt)+]) => {$crate::fps::formal_power_series::Fps::<_, $($tpe)+>::new($crate::list![$($args)+])}; } } pub mod conv_anymod { use crate::{ arraylist::List, fps::{ convolution::convolution_anymod, formal_power_series::{Convolution, Fps}, }, independent::integer::Int, modulo::{Modulus, StaticModInt}, }; #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] pub enum ConvolutionAnyMod {} impl<M: Modulus> Convolution<StaticModInt<M>> for ConvolutionAnyMod { fn convolution(a: &[StaticModInt<M>], b: &[StaticModInt<M>]) -> List<StaticModInt<M>> { convolution_anymod(a, b) } } #[macro_export] macro_rules! fps_anymod { ($($args:tt)+) => {$crate::fps!([$($args)+] [$crate::fps::conv_anymod::ConvolutionAnyMod])}; } } pub mod convolution { use crate::{ arraylist::List, independent::integer::Int, modint, modulo::{ButterflyCache, Modulus, StaticModInt}, nums::*, }; fn prepare<M: Modulus>() -> ButterflyCache<M> { let g = StaticModInt::<M>::raw(primitive_root(M::M as i32) as u32); let mut es = [StaticModInt::<M>::raw(0); 30]; let mut ies = [StaticModInt::<M>::raw(0); 30]; let cnt2 = (M::M - 1).trailing_zeros() as usize; let mut e = g.pow((M::M - 1) >> cnt2); let mut ie = e.inv(); for i in (2..=cnt2).rev() { es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } let sum_e = es .iter() .scan(StaticModInt::new(1), |acc, e| { *acc *= *e; Some(*acc) }) .collect(); let sum_ie = ies .iter() .scan(StaticModInt::new(1), |acc, ie| { *acc *= *ie; Some(*acc) }) .collect(); ButterflyCache { sum_e, sum_ie } } fn butterfly<M: Modulus>(a: &mut [StaticModInt<M>]) { let n = a.len(); let h = ceil_pow2(n as u32); M::butterfly_cache().with(|cache| { let mut cache = cache.borrow_mut(); let ButterflyCache { sum_e, .. } = cache.get_or_insert_with(prepare); for ph in 1..=h { let w = 1 << (ph - 1); let p = 1 << (h - ph); let mut now = StaticModInt::<M>::new(1); for s in 0..w { let offset = s << (h - ph + 1); for i in 0..p { let l = a[i + offset]; let r = a[i + offset + p] * now; a[i + offset] = l + r; a[i + offset + p] = l - r; } now *= sum_e[(!s).trailing_zeros() as usize]; } } }); } fn butterfly_inv<M: Modulus>(a: &mut [StaticModInt<M>]) { let n = a.len(); let h = ceil_pow2(n as u32); M::butterfly_cache().with(|cache| { let mut cache = cache.borrow_mut(); let ButterflyCache { sum_ie, .. } = cache.get_or_insert_with(prepare); for ph in (1..=h).rev() { let w = 1 << (ph - 1); let p = 1 << (h - ph); let mut inow = StaticModInt::<M>::new(1); for s in 0..w { let offset = s << (h - ph + 1); for i in 0..p { let l = a[i + offset]; let r = a[i + offset + p]; a[i + offset] = l + r; a[i + offset + p] = StaticModInt::new(M::M + l.val - r.val) * inow; } inow *= sum_ie[(!s).trailing_zeros() as usize]; } } }) } pub fn convolution_naive<T: Int>(a: &[T], b: &[T]) -> List<T> { if a.is_empty() || b.is_empty() { return vec![].into(); } let (n, m) = (a.len(), b.len()); let (n, m, a, b) = if n < m { (m, n, b, a) } else { (n, m, a, b) }; let mut ans = vec![T::zero(); n + m - 1]; for i in 0..n { for j in 0..m { ans[i + j] += a[i] * b[j]; } } ans.into() } pub fn convolution_ntt<M: Modulus>( a: &[StaticModInt<M>], b: &[StaticModInt<M>], ) -> List<StaticModInt<M>> { if a.is_empty() || b.is_empty() { return vec![].into(); } let (n, m) = (a.len(), b.len()); if n.min(m) <= 60 { return convolution_naive(a, b); } let (mut a, mut b) = (a.to_owned(), b.to_owned()); let z = 1 << ceil_pow2((n + m - 1) as _); a.resize(z, StaticModInt::raw(0)); butterfly(&mut a); b.resize(z, StaticModInt::raw(0)); butterfly(&mut b); for (a, b) in a.iter_mut().zip(&b) { *a *= *b; } butterfly_inv(&mut a); a.resize(n + m - 1, StaticModInt::raw(0)); let iz = StaticModInt::new(z).inv(); for a in &mut a { *a *= iz; } a.into() } fn convolution_raw_mod<T: Int, M: Modulus>(a: &[T], b: &[T]) -> List<StaticModInt<M>> { let a = a .iter() .cloned() .map(StaticModInt::<M>::new) .collect::<Vec<_>>(); let b = b .iter() .cloned() .map(StaticModInt::<M>::new) .collect::<Vec<_>>(); convolution_ntt::<M>(&a, &b) } pub fn convolution_anymod<M: Modulus>( a: &[StaticModInt<M>], b: &[StaticModInt<M>], ) -> List<StaticModInt<M>> { const M1: u32 = 998244353; const M2: u32 = 1012924417; const M3: u32 = 924844033; modint!(M1); modint!(M2); modint!(M3); let a = a.iter().map(StaticModInt::to_u32).collect::<Vec<_>>(); let b = b.iter().map(StaticModInt::to_u32).collect::<Vec<_>>(); let v1 = convolution_raw_mod::<_, M1>(&a, &b); let v2 = convolution_raw_mod::<_, M2>(&a, &b); let v3 = convolution_raw_mod::<_, M3>(&a, &b); let (_, f2f1) = inv_gcd(M1 as _, M2 as _); let (_, f3f1) = inv_gcd(M1 as _, M3 as _); let (_, f3f2) = inv_gcd(M2 as _, M3 as _); v1.into_iter() .zip(v2) .zip(v3) .map(|((e1, e2), e3)| { let x1 = e1; let x2 = (e2 - x1.val.into()) * f2f1.into(); let x3 = ((e3 - x1.val.into()) * f3f1.into() - x2.val.into()) * f3f2.into(); StaticModInt::<M>::new(x1.val) + StaticModInt::<M>::new(x2.val) * M1.into() + StaticModInt::<M>::new(x3.val) * M1.into() * M2.into() }) .collect() } } } pub mod modulo { use crate::nums::inv_gcd; use crate::{impl_integer_functions, independent::integer::Int}; use std::cell::RefCell; use std::fmt::Debug; use std::marker::PhantomData; use std::ops::*; use std::sync::atomic::{self, AtomicU32}; use std::thread::LocalKey; pub trait Modulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord { const M: u32; const HINT_M_IS_PRIME: bool; fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>; } pub trait DynamicModulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord { fn state() -> &'static AtomicU32 { static M: AtomicU32 = AtomicU32::new(1_000_000_007); &M } fn update(m: u32) { Self::state().store(m, atomic::Ordering::SeqCst) } fn umod() -> u32 { Self::state().load(atomic::Ordering::SeqCst) } } #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] pub enum DefaultId {} impl DynamicModulus for DefaultId {} macro_rules! impl_from_for_modint { ($name:ident, $guard: ident, $($tpe:ident),*) => { $( impl<T: $guard> From<$tpe> for $name<T> { fn from(n: $tpe) -> Self { Self::new(n) } } )* }; } macro_rules! impl_assign { ($name:ident, $guard:ident, $($t1:ty, $t2:ty, $fa:ident, $f:ident),*) => { $( impl<T: $guard> $t1 for $name<T> { type Output = Self; #[inline] fn $f(self, other: Self) -> Self { <Self as ModInt>::$f(self, other) } } impl<T: $guard> $t2 for $name<T> { #[inline] fn $fa(&mut self, other: Self) { *self = <Self as ModInt>::$f(*self, other); } } )* }; } macro_rules! impl_modint_structs { ($name:ident, $guard:ident) => { #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] #[repr(transparent)] pub struct $name<T> { pub val: u32, phantom: PhantomData<fn() -> T>, } impl<T> Debug for $name<T> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { self.val.fmt(f) } } impl<T: $guard> $name<T> { #[inline] pub fn new<U: Int>(a: U) -> Self { <Self as ModInt>::new(a) } #[inline] pub fn inv(self) -> Self { <Self as ModInt>::inv(self) } #[inline] pub fn raw(val: u32) -> Self { Self { val, phantom: PhantomData, } } #[inline] pub fn pow<U: Int>(self, x: U) -> Self { <Self as ModInt>::pow(self, x) } } impl<T> std::fmt::Display for $name<T> { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.val) } } impl_from_for_modint!( $name, $guard, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize ); impl_assign!( $name, $guard, Add, AddAssign, add_assign, add, Sub, SubAssign, sub_assign, sub, Mul, MulAssign, mul_assign, mul, Div, DivAssign, div_assign, div, Rem, RemAssign, rem_assign, rem ); impl<T: $guard> Int for $name<T> { impl_integer_functions!(|s: &Self| s.val, |x| Self::new(x), |s: &Self, n: i64| s .pow(n)); } }; } impl_modint_structs!(StaticModInt, Modulus); impl_modint_structs!(DynamicModInt, DynamicModulus); #[macro_export] macro_rules! modint { () => {$crate::modint!(1000000007, true);}; ($m:literal) => {$crate::modint!($m, true);}; ($m:literal, $is_prime:literal) => { $crate::modint!($m, ModValue, $is_prime); #[allow(dead_code)] type Z = $crate::modulo::StaticModInt<ModValue>; }; ($name:ident) => { $crate::modint!($name, $name, true); }; ($value:expr, $name:ident, $is_prime:literal) => { #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] pub enum $name {} impl $crate::modulo::Modulus for $name { const M: u32 = $value as _; const HINT_M_IS_PRIME: bool = $is_prime; fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<Self>>>> { thread_local! { static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<$name>>> = ::std::default::Default::default(); } &BUTTERFLY_CACHE } } }; } pub type D = DynamicModInt<DefaultId>; pub trait ModInt: Int { fn new<U: Int>(val: U) -> Self { let x = val.to_i128(); Self::raw(x.rem_euclid(Self::modulus() as i128) as _) } fn inv(self) -> Self { if Self::mod_is_prime() { Self::pow(self, Self::modulus() - 2) } else { let (g, x) = inv_gcd(Self::val(self) as _, Self::modulus() as _); if g != 1 { panic!("the multiplicative inverse does not exist"); } else { Self::new(x) } } } fn raw(val: u32) -> Self; fn val(self) -> u32; fn modulus() -> u32; fn mod_is_prime() -> bool; fn add(self, other: Self) -> Self { let mut ret = self.val() + other.val(); if ret >= Self::modulus() { ret -= Self::modulus(); } Self::raw(ret) } fn sub(self, other: Self) -> Self { let mut ret = self.val().wrapping_sub(other.val()); if ret >= Self::modulus() { ret = ret.wrapping_add(Self::modulus()); } Self::raw(ret) } fn mul(self, other: Self) -> Self { Self::raw( (u64::from(self.val()) * u64::from(other.val()) % u64::from(Self::modulus())) as _, ) } fn div(self, other: Self) -> Self { self * other.inv() } fn rem(self, other: Self) -> Self { Self::raw(self.val() % other.val()) } fn pow<U: Int>(self, x: U) -> Self { let mut n = x.to_i64(); let mut a = self; let mut res = Self::raw(1); while n > 0 { if n & 1 == 1 { res *= a; } a = a * a; n >>= 1; } res } } impl<M: Modulus> ModInt for StaticModInt<M> { fn raw(val: u32) -> Self { Self::raw(val) } fn val(self) -> u32 { self.val } fn modulus() -> u32 { M::M } fn mod_is_prime() -> bool { M::HINT_M_IS_PRIME } } impl<M: DynamicModulus> ModInt for DynamicModInt<M> { fn raw(val: u32) -> Self { Self::raw(val) } fn val(self) -> u32 { self.val } fn modulus() -> u32 { M::umod() } fn mod_is_prime() -> bool { false } } pub struct ButterflyCache<T> { pub sum_e: Vec<StaticModInt<T>>, pub sum_ie: Vec<StaticModInt<T>>, } } pub mod nums { use std::mem::swap; pub fn ceil_pow2(n: u32) -> u32 { 32 - n.saturating_sub(1).leading_zeros() } pub fn inv_gcd(a: i64, b: i64) -> (i64, i64) { let a = a.rem_euclid(b); if a == 0 { return (b, 0); } let mut s = b; let mut t = a; let mut m0 = 0; let mut m1 = 1; while t != 0 { let u = s / t; s -= t * u; m0 -= m1 * u; swap(&mut s, &mut t); swap(&mut m0, &mut m1); } if m0 < 0 { m0 += b / s; } (s, m0) } pub fn primitive_root(m: i32) -> i32 { match m { 2 => return 1, 167_772_161 => return 3, 469_762_049 => return 3, 754_974_721 => return 11, 998_244_353 => return 3, _ => {} } let mut divs = [0; 20]; divs[0] = 2; let mut cnt = 1; let mut x = (m - 1) / 2; while x % 2 == 0 { x /= 2; } for i in (3..std::i32::MAX).step_by(2) { if i as i64 * i as i64 > x as i64 { break; } if x % i == 0 { divs[cnt] = i; cnt += 1; while x % i == 0 { x /= i; } } } if x > 1 { divs[cnt] = x; cnt += 1; } let mut g = 2; loop { if (0..cnt).all(|i| pow_mod(g as _, ((m - 1) / divs[i]) as _, m as _) != 1) { break g as i32; } g += 1; } } pub fn pow_mod(mut a: i64, mut n: i64, m: i64) -> i64 { let mut res = 1; a %= m; while n > 0 { if n & 1 == 1 { res *= a; res %= m; } a = (a * a) % m; n >>= 1; } res } } pub mod independent { pub mod integer { use std::fmt::Display; use std::ops::*; pub trait Int: Add<Output = Self> + Sub<Output = Self> + Mul<Output = Self> + Div<Output = Self> + Rem<Output = Self> + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + std::hash::Hash + PartialEq + Eq + PartialOrd + Ord + Copy + Display { fn to_u8(&self) -> u8; fn to_u16(&self) -> u16; fn to_u32(&self) -> u32; fn to_u64(&self) -> u64; fn to_u128(&self) -> u128; fn to_i8(&self) -> i8; fn to_i16(&self) -> i16; fn to_i32(&self) -> i32; fn to_i64(&self) -> i64; fn to_i128(&self) -> i128; fn to_usize(&self) -> usize; fn to_isize(&self) -> isize; fn from_u8(x: u8) -> Self; fn from_u16(x: u16) -> Self; fn from_u32(x: u32) -> Self; fn from_u64(x: u64) -> Self; fn from_u128(x: u128) -> Self; fn from_i8(x: i8) -> Self; fn from_i16(x: i16) -> Self; fn from_i32(x: i32) -> Self; fn from_i64(x: i64) -> Self; fn from_i128(x: i128) -> Self; fn from_usize(x: usize) -> Self; fn from_isize(x: isize) -> Self; fn zero() -> Self; fn one() -> Self; fn next(&self) -> Self { *self + Self::one() } fn powint(&self, n: i64) -> Self; } #[macro_export] macro_rules! impl_integer_functions { ($to_op:expr, $from_op:expr, $pow:expr) => { impl_integer_functions!( $to_op, $from_op, $pow, to_u8, from_u8, u8, to_u16, from_u16, u16, to_u32, from_u32, u32, to_u64, from_u64, u64, to_u128, from_u128, u128, to_i8, from_i8, i8, to_i16, from_i16, i16, to_i32, from_i32, i32, to_i64, from_i64, i64, to_i128, from_i128, i128, to_usize, from_usize, usize, to_isize, from_isize, isize ); }; ($to_op:expr, $from_op:expr, $pow:expr, $($tofn:ident, $fromfn:ident, $tpe:ident),*) => { $( fn $tofn(&self) -> $tpe { $to_op(self) as $tpe } fn $fromfn(x: $tpe) -> Self { $from_op(x) } )* fn zero() -> Self {$from_op(0)} fn one() -> Self {$from_op(1)} fn powint(&self, n: i64) -> Self {$pow(self, n)} }; } macro_rules! impl_integer { ($($tpe:ident),*) => { $( impl Int for $tpe { impl_integer_functions!( |s: &Self| *s, |x| x as $tpe, |s: &Self, n: i64| s.pow(n as u32) ); } )* }; } impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize); } } pub mod ext { pub mod option { pub trait UncheckedUnwrap<T> { fn get(self) -> T; } impl<T> UncheckedUnwrap<T> for Option<T> { #[inline] fn get(self) -> T { if cfg!(debug_assertions) { self.unwrap() } else if let Some(value) = self { value } else { unsafe { core::hint::unreachable_unchecked() } } } } } } pub mod macros { pub mod assign_simple { #[macro_export] macro_rules! assign_simple { (($left:expr) $op:tt $right:expr) => { let tmp = $right; $left $op tmp; } } } } pub mod arraylist { use std::ops::*; use std::slice::Iter; use std::fmt::Formatter; use std::iter::FromIterator; use crate::ext::option::UncheckedUnwrap; #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] pub struct List<T> { pub data: Vec<T>, } impl<T> List<T> { #[inline] pub fn new() -> List<T> { List { data: vec![] } } #[inline] pub fn init(init: T, n: isize) -> List<T> where T: Clone, { List { data: vec![init; n as usize], } } #[inline] pub fn pop(&mut self) -> Option<T> { self.data.pop() } #[inline] pub fn append(&mut self, other: &lst<T>) where T: Clone, { self.data.append(&mut other.to_vec()); } #[inline] pub fn resize(&mut self, new_len: isize, value: T) where T: Clone, { self.data.resize(new_len as usize, value); } } macro_rules! impl_idx { ($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => { $(impl<$t> Index<$tpe> for List<$t> { type Output = $($output)+; #[inline] fn index(&$slf, $index: $tpe) -> &Self::Output {$f} })* $(impl<$t> Index<$tpe> for lst<$t> { type Output = $($output)+; #[inline] fn index(&$slf, $index: $tpe) -> &Self::Output {$f} })* } } macro_rules! impl_idx_mut { ($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => { $(impl<T> IndexMut<$tpe> for List<T> { #[inline] fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f} })* $(impl<T> IndexMut<$tpe> for lst<T> { #[inline] fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f} })* }; } macro_rules! impl_idx_slice { ($($tpe:ty),*) => { impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*); impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*); }; } impl_idx! { isize, T [T], self, i, self.at(i), char, T [T], self, i, self.at(i as isize - 'a' as isize) } impl_idx_slice! { Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize> } impl_idx_mut! { isize, self, i, self.at_mut(i), char, self, i, self.at_mut(i as isize - 'a' as isize) } impl<T> FromIterator<T> for List<T> { #[inline] fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self { List { data: iter.into_iter().collect(), } } } impl<T> IntoIterator for List<T> { type Item = T; type IntoIter = std::vec::IntoIter<T>; #[inline] fn into_iter(self) -> std::vec::IntoIter<T> { self.data.into_iter() } } macro_rules! impl_traits { ($($tpe:tt),*) => { $( impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" ")) } } impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> { fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { self.data.fmt(f) } } impl<'a, T> IntoIterator for &'a $tpe<T> { type Item = &'a T; type IntoIter = Iter<'a, T>; #[inline] fn into_iter(self) -> Iter<'a, T> { self.iter() } } )* }; } impl_traits!(List, lst); impl<T> From<Vec<T>> for List<T> { #[inline] fn from(vec: Vec<T>) -> Self { List { data: vec } } } impl<T: Clone> From<&[T]> for List<T> { #[inline] fn from(slice: &[T]) -> Self { slice.iter().cloned().collect() } } impl<T> Deref for List<T> { type Target = lst<T>; #[inline] fn deref(&self) -> &lst<T> { lst::new(&self.data) } } impl<T> DerefMut for List<T> { #[inline] fn deref_mut(&mut self) -> &mut lst<T> { lst::new_mut(&mut self.data) } } #[macro_export] macro_rules! list { () => { $crate::arraylist::List::new() }; ($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) }; ($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)}; ($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) }; } #[allow(non_camel_case_types)] #[derive(PartialEq, Eq, PartialOrd, Ord)] #[repr(transparent)] pub struct lst<T> { data: [T], } impl<T> lst<T> { #[inline] pub fn new(slice: &[T]) -> &Self { unsafe { &*(slice as *const [T] as *const Self) } } #[inline] pub fn new_mut(slice: &mut [T]) -> &mut Self { unsafe { &mut *(slice as *mut [T] as *mut Self) } } #[inline] pub fn lens(&self) -> isize { self.data.len() as isize } #[inline] pub fn list(&self) -> List<T> where T: Clone, { self.cloned().collect() } #[inline] fn at(&self, index: isize) -> &T { if cfg!(debug_assertions) { self.data.index(index as usize) } else { unsafe { self.data.get_unchecked(index as usize) } } } #[inline] fn at_mut(&mut self, index: isize) -> &mut T { if cfg!(debug_assertions) { self.data.index_mut(index as usize) } else { unsafe { self.data.get_unchecked_mut(index as usize) } } } #[inline] pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> { if cfg!(debug_assertions) { lst::new(self.data.index(self.rgm(range))) } else { unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) } } } #[inline] pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> { if cfg!(debug_assertions) { lst::new_mut(self.data.index_mut(self.rgm(range))) } else { let r = self.rgm(range); unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) } } } #[inline] pub fn cloned(&self) -> std::iter::Cloned<Iter<T>> where T: Clone, { self.iter().cloned() } #[inline] pub fn map<B, F>(&self, f: F) -> List<B> where T: Clone, F: FnMut(T) -> B, { self.cloned().map(f).collect() } #[inline] fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> { (match r.start_bound() { Bound::Included(x) => *x as usize, Bound::Excluded(x) => *x as usize + 1, _ => 0, }) .max(0)..(match r.end_bound() { Bound::Included(x) => *x as usize + 1, Bound::Excluded(x) => *x as usize, _ => self.len(), }) .min(self.len()) } #[inline] pub fn first_exn(&self) -> &T { self.first().get() } } impl lst<isize> {} impl<T> Deref for lst<T> { type Target = [T]; #[inline] fn deref(&self) -> &[T] { &self.data } } impl<T> DerefMut for lst<T> { #[inline] fn deref_mut(&mut self) -> &mut [T] { &mut self.data } } impl<'a, T> From<&'a [T]> for &'a lst<T> { #[inline] fn from(slice: &'a [T]) -> Self { lst::new(slice) } } } pub mod scanner { use std::io::{stdin, BufReader, Bytes, Read, Stdin}; use std::str::FromStr; pub struct Scanner { buf: Bytes<BufReader<Stdin>>, } impl Scanner { pub fn new() -> Scanner { Scanner { buf: BufReader::new(stdin()).bytes(), } } #[inline] fn token<T: std::iter::FromIterator<char>>(&mut self) -> T { self.buf .by_ref() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect() } #[inline] pub fn read<T: FromStr>(&mut self) -> T { self.string().parse().ok().unwrap() } #[inline] pub fn string(&mut self) -> String { self.token() } #[inline] pub fn int(&mut self) -> isize { self.read() } } }