#1019555 (Rust) No.2926 Botaoshi

提出ソース

結果

問題	No.2926 Botaoshi
ユーザー	naut3
提出日時	2024-10-14 19:18:04
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	7 ms / 2,000 ms
コード長	6,717 bytes
コンパイル時間	13,905 ms
コンパイル使用メモリ	377,968 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-10-14 19:18:20
合計ジャッジ時間	15,328 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	7 ms 5,248 KB
testcase_13	AC	6 ms 5,248 KB
testcase_14	AC	7 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	5 ms 5,248 KB
testcase_17	AC	6 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	5 ms 5,248 KB
testcase_20	AC	3 ms 5,248 KB
testcase_21	AC	3 ms 5,248 KB
testcase_22	AC	4 ms 5,248 KB
testcase_23	AC	1 ms 5,248 KB
testcase_24	AC	5 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	6 ms 5,248 KB
testcase_27	AC	4 ms 5,248 KB
testcase_28	AC	1 ms 5,248 KB
testcase_29	AC	1 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	5 ms 5,248 KB
testcase_34	AC	4 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	6 ms 5,248 KB
testcase_37	AC	6 ms 5,376 KB
testcase_38	AC	7 ms 5,248 KB
testcase_39	AC	7 ms 5,376 KB
testcase_40	AC	6 ms 5,248 KB
testcase_41	AC	6 ms 5,248 KB
testcase_42	AC	7 ms 5,376 KB
testcase_43	AC	7 ms 5,248 KB
testcase_44	AC	6 ms 5,248 KB
testcase_45	AC	6 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(non_snake_case, unused_must_use, unused_imports)]
use std::io::{self, prelude::*};
use std::{fmt::*, ops::*};

fn main() {
    let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout());
    let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock()));
    macro_rules! input {
        ($t: ty, $n: expr) => {
            (0..$n).map(|_| input!($t)).collect::<Vec<_>>()
        };
        ($t: ty) => {
            stdin.next().unwrap().parse::<$t>().unwrap()
        };
    }

    let N = input!(usize);
    let S = input!(String).chars().collect::<Vec<_>>();
    type MInt = ModInt<998244353>;

    let mut dp = vec![[MInt::default(); 3]; N];

    match S[0] {
        'L' => {
            dp[0][0] += 1;
        }
        'R' => {
            dp[0][1] += 1;
        }
        'U' => {
            dp[0][2] += 1;
        }
        '.' => {
            dp[0][0] += 1;
            dp[0][1] += 1;
            dp[0][2] += 1;
        }
        _ => unreachable!(),
    }

    for i in 1..N {
        match S[i] {
            'L' => {
                dp[i][0] = dp[i - 1][0] + dp[i - 1][2];
            }
            'R' => {
                dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            }
            'U' => {
                dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            }
            '.' => {
                dp[i][0] = dp[i - 1][0] + dp[i - 1][2];
                dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
                dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            }
            _ => unreachable!(),
        }
    }

    writeln!(buffer, "{}", dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]);
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, Default)]
pub struct ModInt<const P: u32>(u32);

impl<const P: u32> ModInt<P> {
    pub fn from_raw(value: u32) -> Self {
        assert!(value < P);
        Self(value)
    }

    pub fn pow(&self, mut x: u32) -> Self {
        let mut a = *self;
        let mut r = Self::from_raw(1);

        while x > 0 {
            if x & 1 == 1 {
                r *= a;
            }

            a *= a;
            x >>= 1;
        }

        r
    }

    pub fn inv(&self) -> Self {
        self.pow(P - 2)
    }
}

impl<const P: u32> Add for ModInt<P> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        Self((self.0 + rhs.0) % P)
    }
}

impl<const P: u32> Sub for ModInt<P> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        Self((P + self.0 - rhs.0) % P)
    }
}

impl<const P: u32> Mul for ModInt<P> {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Self(((self.0 as u64 * rhs.0 as u64) % P as u64) as u32)
    }
}

impl<const P: u32> Div for ModInt<P> {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}

impl<const P: u32> AddAssign for ModInt<P> {
    fn add_assign(&mut self, rhs: Self) {
        self.0 += rhs.0;
        self.0 %= P;
    }
}

impl<const P: u32> SubAssign for ModInt<P> {
    fn sub_assign(&mut self, rhs: Self) {
        self.0 += P - rhs.0;
        self.0 %= P;
    }
}

impl<const P: u32> MulAssign for ModInt<P> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = self.clone() * rhs;
    }
}

impl<const P: u32> DivAssign for ModInt<P> {
    fn div_assign(&mut self, rhs: Self) {
        *self *= rhs.inv()
    }
}

impl<const P: u32> Neg for ModInt<P> {
    type Output = Self;
    fn neg(self) -> Self::Output {
        Self((P - self.0) % P)
    }
}

impl<const P: u32> Display for ModInt<P> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        write!(f, "{}", self.0)
    }
}

macro_rules! impl_op_for_modint {
    ($($t: ty), *) => {
        $(
            impl<const P: u32> From<$t> for ModInt<P> {
                fn from(value: $t) -> Self {
                    Self((P as $t + value % P as $t) as u32 % P)
                }
            }

            impl<const P: u32> Add<$t> for ModInt<P> {
                type Output = Self;
                fn add(self, rhs: $t) -> Self::Output {
                    self + Self::from(rhs)
                }
            }

            impl<const P: u32> Add<ModInt<P>> for $t {
                type Output = ModInt<P>;
                fn add(self, rhs: ModInt<P>) -> Self::Output {
                    Self::Output::from(self) + rhs
                }
            }

            impl<const P: u32> Sub<$t> for ModInt<P> {
                type Output = Self;
                fn sub(self, rhs: $t) -> Self::Output {
                    self - Self::from(rhs)
                }
            }

            impl<const P: u32> Sub<ModInt<P>> for $t {
                type Output = ModInt<P>;
                fn sub(self, rhs: ModInt<P>) -> Self::Output {
                    Self::Output::from(self) - rhs
                }
            }

            impl<const P: u32> Mul<$t> for ModInt<P> {
                type Output = Self;
                fn mul(self, rhs: $t) -> Self::Output {
                    self * Self::from(rhs)
                }
            }

            impl<const P: u32> Mul<ModInt<P>> for $t {
                type Output = ModInt<P>;
                fn mul(self, rhs: ModInt<P>) -> Self::Output {
                    Self::Output::from(self) * rhs
                }
            }

            impl<const P: u32> Div<$t> for ModInt<P> {
                type Output = Self;
                fn div(self, rhs: $t) -> Self::Output {
                    self / Self::from(rhs)
                }
            }

            impl<const P: u32> Div<ModInt<P>> for $t {
                type Output = ModInt<P>;
                fn div(self, rhs: ModInt<P>) -> Self::Output {
                    Self::Output::from(self) / rhs
                }
            }

            impl<const P: u32> AddAssign<$t> for ModInt<P> {
                fn add_assign(&mut self, rhs: $t) {
                    *self += Self::from(rhs)
                }
            }

            impl<const P: u32> SubAssign<$t> for ModInt<P> {
                fn sub_assign(&mut self, rhs: $t) {
                    *self -= Self::from(rhs)
                }
            }

            impl<const P: u32> MulAssign<$t> for ModInt<P> {
                fn mul_assign(&mut self, rhs: $t) {
                    *self *= Self::from(rhs)
                }
            }

            impl<const P: u32> DivAssign<$t> for ModInt<P> {
                fn div_assign(&mut self, rhs: $t) {
                    *self /= Self::from(rhs)
                }
            }
        )*
    };
}

impl_op_for_modint!(usize, isize, u64, i64, u32, i32);

yukicoder

結果

テストケース

ソースコード