#1019555 (Rust) No.2926 Botaoshi

• 問題: No.2926 Botaoshi
• ユーザー: naut3
• 提出日時: 2024-10-14 19:18:04
• 言語: Rust (1.83.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

ファイルパターン	結果
sample	AC * 4
other	AC * 42

ソースコード

#![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);