結果
問題 | No.2023 Tiling is Fun |
ユーザー |
![]() |
提出日時 | 2022-07-29 23:16:25 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 21,600 bytes |
コンパイル時間 | 17,958 ms |
コンパイル使用メモリ | 384,352 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 16:43:44 |
合計ジャッジ時間 | 18,999 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#![allow(unused_imports)]use input::*;use std::{collections::*,io::{self, BufWriter, Write},};fn run<I: Input, O: Write>(mut ss: I, mut out: O) {let t: u32 = 1;for _ in 0..t {case(&mut ss, &mut out);}}def_mint!(998244353);fn case<I: Input, O: Write>(mut ss: I, mut out: O) {use fact::*;use mod_int::*;let (a, b): (usize, usize) = ss.parse();let f = Fact::<MintModulo>::new(a + b);let ans = f.binom(a + b - 2, a - 1);wln!(out, "{}", ans);}fn main() {let stdin = io::stdin();let ss = SplitWs::new(stdin.lock());let stdout = io::stdout();let out = BufWriter::new(stdout.lock());run(ss, out);}pub mod fact {use super::mod_int::*;pub struct Fact<M> {f: Vec<ModInt<M>>,finv: Vec<ModInt<M>>,}impl<M: Modulo> Fact<M> {pub fn new(n: usize) -> Self {let mut f = vec![ModInt::new(0); n + 1];f[0] = ModInt::new(1);for i in 1..=n {f[i] = ModInt::new(i as u32) * f[i - 1];}let mut finv = vec![ModInt::new(0); n + 1];finv[n] = f[n].inv();for i in (1..=n).rev() {finv[i - 1] = finv[i] * ModInt::new(i as u32);}Self { f, finv }}pub fn fact(&self, x: usize) -> ModInt<M> {self.f[x]}pub fn fact_inv(&self, x: usize) -> ModInt<M> {self.finv[x]}pub fn binom(&self, n: usize, k: usize) -> ModInt<M> {if n >= k {self.fact(n) * self.fact_inv(n - k) * self.fact_inv(k)} else {ModInt::new(0)}}pub fn perm(&self, n: usize, k: usize) -> ModInt<M> {if n >= k {self.fact(n) * self.fact_inv(n - k)} else {ModInt::new(0)}}}}pub mod mod_int {use std::{cmp,fmt::{self, Debug, Display},hash::Hash,iter::{Product, Sum},marker::PhantomData,mem,ops::*,};pub struct ModInt<M> {x: u32,marker: PhantomData<*const M>,}pub trait Modulo {fn modulo() -> u32;}impl<M> ModInt<M> {pub fn new(x: u32) -> Self {Self {x,marker: PhantomData,}}pub fn get(self) -> u32 {self.x}}impl<M: Modulo> ModInt<M> {pub fn modulo() -> u32 {M::modulo()}pub fn normalize(self) -> Self {Self::new(self.x % M::modulo())}pub fn inv(self) -> Self {assert_ne!(self.get(), 0);self.pow(M::modulo() - 2)}pub fn twice(self) -> Self {self + self}pub fn half(self) -> Self {if self.x & 1 == 0 {Self::new(self.x >> 1)} else {Self::new((self.x >> 1) + ((Self::modulo() + 1) >> 1))}}}impl<M> Clone for ModInt<M> {fn clone(&self) -> Self {Self::new(self.x)}}impl<M> Copy for ModInt<M> {}impl<M: Modulo> Neg for ModInt<M> {type Output = Self;fn neg(self) -> Self {Self::new(if self.x != 0 { M::modulo() - self.x } else { 0 })}}impl<M: Modulo> Neg for &ModInt<M> {type Output = ModInt<M>;fn neg(self) -> Self::Output {-(*self)}}impl<M: Modulo> Add for ModInt<M> {type Output = Self;fn add(self, rhs: Self) -> Self {let x = self.x + rhs.x;Self::new(if x < M::modulo() { x } else { x - M::modulo() })}}impl<M: Modulo> Sub for ModInt<M> {type Output = Self;fn sub(self, rhs: Self) -> Self {let x = if self.x >= rhs.x {self.x - rhs.x} else {M::modulo() + self.x - rhs.x};Self::new(x)}}impl<M: Modulo> Mul for ModInt<M> {type Output = Self;fn mul(self, rhs: Self) -> Self {let x = (self.x as u64 * rhs.x as u64) % M::modulo() as u64;Self::new(x as u32)}}impl<M: Modulo> Div for ModInt<M> {type Output = Self;#[allow(clippy::suspicious_arithmetic_impl)]fn div(self, rhs: Self) -> Self {self * rhs.inv()}}macro_rules! biops {($ Op : ident , $ op : ident , $ OpAssign : ident , $ op_assign : ident) => {impl<M: Modulo> $Op<&Self> for ModInt<M> {type Output = Self;fn $op(self, rhs: &Self) -> Self {self.$op(*rhs)}}impl<M: Modulo> $Op<ModInt<M>> for &ModInt<M> {type Output = ModInt<M>;fn $op(self, rhs: ModInt<M>) -> ModInt<M> {(*self).$op(rhs)}}impl<M: Modulo> $Op for &ModInt<M> {type Output = ModInt<M>;fn $op(self, rhs: Self) -> ModInt<M> {(*self).$op(*rhs)}}impl<M: Modulo> $OpAssign for ModInt<M> {fn $op_assign(&mut self, rhs: Self) {*self = self.$op(rhs);}}impl<M: Modulo> $OpAssign<&Self> for ModInt<M> {fn $op_assign(&mut self, rhs: &Self) {*self = self.$op(rhs);}}};}biops!(Add, add, AddAssign, add_assign);biops!(Sub, sub, SubAssign, sub_assign);biops!(Mul, mul, MulAssign, mul_assign);biops!(Div, div, DivAssign, div_assign);impl<M: Modulo> 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> Product for ModInt<M> {fn product<I: Iterator<Item = Self>>(iter: I) -> Self {iter.fold(ModInt::new(1), |x, y| x * y)}}macro_rules! fold {($ Trait : ident , $ f : ident) => {impl<'a, M: Modulo + 'a> $Trait<&'a ModInt<M>> for ModInt<M> {fn $f<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {iter.copied().$f()}}};}fold!(Sum, sum);fold!(Product, product);pub trait Pow<Exp> {fn pow(self, exp: Exp) -> Self;}macro_rules! pow {($ uty : ident , $ ity : ident) => {impl<M: Modulo> Pow<$uty> for ModInt<M> {fn pow(self, mut exp: $uty) -> Self {if exp == 0 {return ModInt::new(1);}let mut res = ModInt::new(1);let mut base = self;while exp > 1 {if exp & 1 != 0 {res *= base;}exp >>= 1;base *= base;}base * res}}impl<M: Modulo> Pow<$ity> for ModInt<M> {fn pow(self, exp: $ity) -> Self {if exp >= 0 {self.pow(exp as $uty)} else {self.inv().pow(-exp as $uty)}}}};}macro_rules ! impls { ($ m : ident , $ ($ uty : ident , $ ity : ident) ,*) => { $ ($ m ! ($ uty , $ ity) ;) * } ; }impls!(pow, usize, isize, u8, i8, u16, i16, u32, i32, u64, i64, u128, i128);impl<M> Default for ModInt<M> {fn default() -> Self {Self::new(0)}}impl<M> PartialEq for ModInt<M> {fn eq(&self, other: &Self) -> bool {self.x == other.x}}impl<M> Eq for ModInt<M> {}impl<M> PartialOrd for ModInt<M> {fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {self.x.partial_cmp(&other.x)}}impl<M> Ord for ModInt<M> {fn cmp(&self, other: &Self) -> cmp::Ordering {self.x.cmp(&other.x)}}impl<M> Hash for ModInt<M> {fn hash<H: std::hash::Hasher>(&self, state: &mut H) {self.x.hash(state)}}macro_rules! from_uint {($ ty : ident) => {impl<M: Modulo> From<$ty> for ModInt<M> {fn from(x: $ty) -> Self {if mem::size_of::<$ty>() <= 4 {if ($ty::max_value() as u32) < M::modulo() {Self::new(x as u32)} else {Self::new(x as u32).normalize()}} else {Self::new((x % M::modulo() as $ty) as u32)}}}};}macro_rules ! impls { ($ m : ident , $ ($ ty : ident) ,*) => { $ ($ m ! ($ ty) ;) * } ; }impls!(from_uint, usize, u8, u16, u32, u64, u128);macro_rules! from_small_int {($ ty : ident) => {impl<M: Modulo> From<$ty> for ModInt<M> {fn from(x: $ty) -> Self {let mut x = x as i32;if x >= 0 {Self::from(x as u32)} else {while x < 0 {x += M::modulo() as i32;}Self::new(x as u32)}}}};}impls!(from_small_int, i8, i16, i32);impl<M> Display for ModInt<M> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {Display::fmt(&self.x, f)}}impl<M> Debug for ModInt<M> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {Debug::fmt(&self.x, f)}}#[macro_export]macro_rules! def_mint {($ modulo : expr) => {#[derive(Clone, Copy, PartialEq, Eq, Default, Debug)]pub struct MintModulo;impl crate::mod_int::Modulo for MintModulo {fn modulo() -> u32 {$modulo}}pub type Mint = crate::mod_int::ModInt<MintModulo>;pub fn mint(x: u32) -> Mint {x.into()}};}}pub mod input {use std::{io::{self, prelude::*},marker::PhantomData,mem,};pub trait Input {fn bytes(&mut self) -> &[u8];fn bytes_vec(&mut self) -> Vec<u8> {self.bytes().to_vec()}fn str(&mut self) -> &str {std::str::from_utf8(self.bytes()).unwrap()}fn parse<T: Parse>(&mut self) -> T {self.parse_with(DefaultParser)}fn parse_with<T>(&mut self, mut parser: impl Parser<T>) -> T {parser.parse(self)}fn seq<T: Parse>(&mut self) -> Seq<T, Self, DefaultParser> {self.seq_with(DefaultParser)}fn seq_with<T, P: Parser<T>>(&mut self, parser: P) -> Seq<T, Self, P> {Seq {input: self,parser,marker: PhantomData,}}fn collect<T: Parse, C: std::iter::FromIterator<T>>(&mut self, n: usize) -> C {self.seq().take(n).collect()}}impl<T: Input> Input for &mut T {fn bytes(&mut self) -> &[u8] {(**self).bytes()}}pub trait Parser<T> {fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T;}impl<T, P: Parser<T>> Parser<T> for &mut P {fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {(**self).parse(s)}}pub trait Parse {fn parse<I: Input + ?Sized>(s: &mut I) -> Self;}pub struct DefaultParser;impl<T: Parse> Parser<T> for DefaultParser {fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {T::parse(s)}}pub struct Seq<'a, T, I: ?Sized, P> {input: &'a mut I,parser: P,marker: PhantomData<*const T>,}impl<'a, T, I: Input + ?Sized, P: Parser<T>> Iterator for Seq<'a, T, I, P> {type Item = T;#[inline]fn next(&mut self) -> Option<Self::Item> {Some(self.input.parse_with(&mut self.parser))}fn size_hint(&self) -> (usize, Option<usize>) {(!0, None)}}impl Parse for char {#[inline]fn parse<I: Input + ?Sized>(s: &mut I) -> Self {let s = s.bytes();debug_assert_eq!(s.len(), 1);*s.first().expect("zero length") as char}}macro_rules ! tuple { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse) ,*> Parse for ($ ($ T ,) *) { # [inline] # [allow (unused_variables)] #[allow (clippy :: unused_unit)] fn parse < I : Input + ? Sized > (s : & mut I) -> Self { ($ ($ T :: parse (s) ,) *) } } } ; }tuple!();tuple!(A);tuple!(A, B);tuple!(A, B, C);tuple!(A, B, C, D);tuple!(A, B, C, D, E);tuple!(A, B, C, D, E, F);tuple!(A, B, C, D, E, F, G);#[cfg(feature = "newer")]impl<T: Parse, const N: usize> Parse for [T; N] {fn parse<I: Input + ?Sized>(s: &mut I) -> Self {use std::{mem::MaybeUninit, ptr};struct Guard<T, const N: usize> {arr: [MaybeUninit<T>; N],i: usize,}impl<T, const N: usize> Drop for Guard<T, N> {fn drop(&mut self) {unsafe {ptr::drop_in_place(&mut self.arr[..self.i] as *mut _ as *mut [T]);}}}let mut g = Guard::<T, N> {arr: unsafe { MaybeUninit::uninit().assume_init() },i: 0,};while g.i < N {g.arr[g.i] = MaybeUninit::new(s.parse());g.i += 1;}unsafe { mem::transmute_copy(&g.arr) }}}macro_rules! uint {($ ty : ty) => {impl Parse for $ty {#[inline]fn parse<I: Input + ?Sized>(s: &mut I) -> Self {let s = s.bytes();s.iter().fold(0, |x, d| 10 * x + (0xf & d) as $ty)}}};}macro_rules! int {($ ty : ty) => {impl Parse for $ty {#[inline]fn parse<I: Input + ?Sized>(s: &mut I) -> Self {let f = |s: &[u8]| {s.iter().fold(0 as $ty, |x, d| (10 * x).wrapping_add((0xf & d) as $ty))};let s = s.bytes();if let Some((b'-', s)) = s.split_first() {f(s).wrapping_neg()} else {f(s)}}}};}macro_rules! float {($ ty : ty) => {impl Parse for $ty {fn parse<I: Input + ?Sized>(s: &mut I) -> Self {const POW: [$ty; 18] = [1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,1e14, 1e15, 1e16, 1e17,];let s = s.bytes();let (minus, s) = if let Some((b'-', s)) = s.split_first() {(true, s)} else {(false, s)};let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {(&s[..p], &s[p + 1..])} else {(s, &[][..])};let x = int.iter().chain(fract).fold(0u64, |x, d| 10 * x + (0xf & *d) as u64);let x = x as $ty;let x = if minus { -x } else { x };let exp = fract.len();if exp == 0 {x} else if let Some(pow) = POW.get(exp) {x / pow} else {x / (10.0 as $ty).powi(exp as i32)}}}};}macro_rules! from_bytes {($ ty : ty) => {impl Parse for $ty {#[inline]fn parse<I: Input + ?Sized>(s: &mut I) -> Self {s.bytes().into()}}};}macro_rules! from_str {($ ty : ty) => {impl Parse for $ty {#[inline]fn parse<I: Input + ?Sized>(s: &mut I) -> Self {s.str().into()}}};}macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }impls!(uint, usize, u8, u16, u32, u64, u128);impls!(int, isize, i8, i16, i32, i64, i128);impls!(float, f32, f64);impls!(from_bytes, Vec<u8>, Box<[u8]>);impls!(from_str, String);#[derive(Clone)]pub struct SplitWs<T> {src: T,buf: Vec<u8>,pos: usize,len: usize,}const BUF_SIZE: usize = 1 << 26;impl<T: Read> SplitWs<T> {pub fn new(src: T) -> Self {Self {src,buf: vec![0; BUF_SIZE],pos: 0,len: 0,}}#[inline(always)]fn peek(&self) -> &[u8] {unsafe { self.buf.get_unchecked(self.pos..self.len) }}#[inline(always)]fn consume(&mut self, n: usize) -> &[u8] {let pos = self.pos;self.pos += n;unsafe { self.buf.get_unchecked(pos..self.pos) }}fn read(&mut self) -> usize {self.buf.copy_within(self.pos..self.len, 0);self.len -= self.pos;self.pos = 0;if self.len == self.buf.len() {self.buf.resize(2 * self.buf.len(), 0);}loop {match self.src.read(&mut self.buf[self.len..]) {Ok(n) => {self.len += n;return n;}Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}Err(e) => panic!("io error: {:?}", e),}}}}impl<T: Read> Input for SplitWs<T> {#[inline]fn bytes(&mut self) -> &[u8] {loop {if let Some(del) = self.peek().iter().position(|c| c.is_ascii_whitespace()) {if del > 0 {let s = self.consume(del + 1);return s.split_last().unwrap().1;} else {self.consume(1);}} else if self.read() == 0 {return self.consume(self.len - self.pos);}}}}}pub mod macros {#[macro_export]macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }#[macro_export]macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)]$ dst . flush () . unwrap () ; } } }#[macro_export]macro_rules! w_iter {($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{let mut first = true;for elem in $iter {if first {w!($dst, $fmt, elem);first = false;} else {w!($dst, concat!($delim, $fmt), elem);}}}};($ dst : expr , $ fmt : expr , $ iter : expr) => {w_iter!($dst, $fmt, $iter, " ")};}#[macro_export]macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }#[macro_export]macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }#[macro_export]macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }#[macro_export]#[doc(hidden)]macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat !(__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }#[macro_export]macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*), file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }}