#782650 (Rust) No.2023 Tiling is Fun

提出ソース
結果

問題	No.2023 Tiling is Fun
ユーザー	cotton_fn_
提出日時	2022-07-29 23:16:25
言語	Rust (1.77.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
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	3 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	0 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![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) ,*) ; } } ; }
}
yukicoder

結果

テストケース

ソースコード
