結果

問題 No.3428 Palindromic Path (Easy)
コンテスト
ユーザー urectanc
提出日時 2026-01-11 14:30:28
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 9,857 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,479 ms
コンパイル使用メモリ 411,984 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 14:30:55
合計ジャッジ時間 25,982 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use modint::ModInt998244353;
use proconio::{input, marker::Chars};

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
        c: [Chars; n],
    }

    if c[0][0] != c[n - 1][n - 1] {
        println!("0");
        return;
    }

    let mut dp = vec![vec![Mint::raw(0); n]; n];
    dp[0][0] = 1.into();

    for k in 0..n - 1 {
        let mut ndp = vec![vec![Mint::raw(0); n]; n];
        // i0 + j0 = k, i1 + j1 = 2n - 2 - k
        for x in 0..=k {
            for y in 0..=k {
                let i0 = x;
                let j0 = k - i0;
                let i1 = n - 1 - y;
                let j1 = 2 * n - 2 - k - i1;

                if c[i0 + 1][j0] == c[i1 - 1][j1] {
                    ndp[x + 1][y + 1] += dp[x][y];
                }
                if c[i0][j0 + 1] == c[i1 - 1][j1] {
                    ndp[x][y + 1] += dp[x][y];
                }
                if c[i0 + 1][j0] == c[i1][j1 - 1] {
                    ndp[x + 1][y] += dp[x][y];
                }
                if c[i0][j0 + 1] == c[i1][j1 - 1] {
                    ndp[x][y] += dp[x][y];
                }
            }
        }

        dp = ndp;
    }

    let ans = (0..n).map(|i| dp[i][n - 1 - i]).sum::<Mint>();
    println!("{ans}");
}

#[allow(unused)]
mod modint {
    use std::{
        fmt::Debug,
        ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign},
    };

    const fn gcd_inv(a: i64, b: i64) -> (i64, i64) {
        let a = a.rem_euclid(b);
        if a == 0 {
            return (b, 0);
        }

        // invariant: x.0 = x.1 * a (mod b) for x = u,v
        let mut u = (b, 0);
        let mut v = (a, 1);
        while v.0 != 0 {
            let q = u.0.div_euclid(v.0);
            u.0 -= q * v.0;
            u.1 -= q * v.1;
            (u, v) = (v, u);
        }

        if u.1 < 0 {
            u.1 += b.div_euclid(u.0);
        }

        u
    }

    pub trait Modulus: 'static + Clone + Copy + Debug + PartialEq + Eq {
        const MOD: u32;
    }

    macro_rules! define_modulus {
    ( $( ($name:ident, $modulus:expr) ),* $(,)? ) => { $(
        #[derive(Clone, Copy, Debug, PartialEq, Eq)]
        pub struct $name;
        impl Modulus for $name {
            // TODO: use inline const for static assertion in Rust >= 1.79
            // const MOD: u32 = const { assert!($modulus < (1u32 << 31)); $modulus };
            const MOD: u32 = $modulus;
        }
    )* };
}

    define_modulus!((Mod998244353, 998244353), (Mod1000000007, 1000000007));

    #[derive(Clone, Copy, PartialEq, Eq, Hash)]
    pub struct StaticModInt<M> {
        val: u32,
        _phantom: std::marker::PhantomData<fn() -> M>,
    }

    impl<M: Modulus> StaticModInt<M> {
        pub const fn modulus() -> u32 {
            M::MOD
        }

        pub const fn new(val: u32) -> Self {
            Self {
                val: val.rem_euclid(Self::modulus()),
                _phantom: std::marker::PhantomData,
            }
        }

        pub const fn raw(val: u32) -> Self {
            Self {
                val,
                _phantom: std::marker::PhantomData,
            }
        }

        pub const fn val(&self) -> u32 {
            self.val
        }

        pub const fn pow(self, mut exp: u64) -> Self {
            let modulus = Self::modulus() as u64;
            let mut base = self.val() as u64;
            let mut acc = 1u64;

            while exp > 0 {
                if exp & 1 == 1 {
                    acc = acc * base % modulus;
                }
                base = base * base % modulus;
                exp >>= 1;
            }

            Self::raw(acc as u32)
        }

        pub const fn inv(self) -> Self {
            // TODO: const Option::expect() is stable for Rust >= 1.83
            // self.checked_inv().expect("")
            let Some(inv) = self.checked_inv() else {
                panic!("the inverse does not exist")
            };
            inv
        }

        pub const fn checked_inv(self) -> Option<Self> {
            let (gcd, inv) = gcd_inv(self.val() as i64, Self::modulus() as i64);
            if gcd == 1 {
                Some(Self::raw(inv as u32))
            } else {
                None
            }
        }

        /// invariant: x.0 = x.1 * val (mod m) for x = u,v
        /// https://en.wikipedia.org/wiki/Rational_reconstruction_(mathematics)
        fn into_rational(&self) -> (i64, i64) {
            let m = Self::modulus() as i64;
            let mut u = (m, 0i64);
            let mut v = (self.val() as i64, 1i64);
            while v.0 * v.0 * 2 > m {
                let q = u.0.div_euclid(v.0);
                let w = (u.0 - q * v.0, u.1 - q * v.1);
                u = std::mem::replace(&mut v, w);
            }
            if v.1 < 0 {
                (-v.0, -v.1)
            } else {
                v
            }
        }
    }

    impl<M: Modulus> std::fmt::Display for StaticModInt<M> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.val)
        }
    }

    impl<M: Modulus> std::fmt::Debug for StaticModInt<M> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let (num, denom) = self.into_rational();
            if denom == 1 {
                write!(f, "{num}")
            } else {
                write!(f, "{num}/{denom}")
            }
        }
    }

    impl<M: Modulus> std::str::FromStr for StaticModInt<M> {
        type Err = std::num::ParseIntError;
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let value = s.parse::<u32>()?;
            Ok(value.into())
        }
    }

    macro_rules! impl_from_integer {
    ( $( $ty:tt ),* ) => { $(
        impl<M: Modulus> From<$ty> for StaticModInt<M> {
            fn from(value: $ty) -> StaticModInt<M> {
                Self::raw((value as $ty).rem_euclid(Self::modulus() as $ty) as u32)
            }
        }
    )* };
}
    impl_from_integer!(u32, u64, usize, i32, i64, isize);

    impl<M: Modulus> std::ops::Neg for StaticModInt<M> {
        type Output = Self;
        fn neg(mut self) -> Self::Output {
            if self.val > 0 {
                self.val = Self::modulus() - self.val;
            }
            self
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> AddAssign<T> for StaticModInt<M> {
        fn add_assign(&mut self, rhs: T) {
            self.val += rhs.into().val;
            if self.val >= Self::modulus() {
                self.val -= Self::modulus();
            }
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> SubAssign<T> for StaticModInt<M> {
        fn sub_assign(&mut self, rhs: T) {
            self.val = self.val.wrapping_sub(rhs.into().val);
            if self.val > Self::modulus() {
                self.val = self.val.wrapping_add(Self::modulus());
            }
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> MulAssign<T> for StaticModInt<M> {
        fn mul_assign(&mut self, rhs: T) {
            self.val = ((self.val as u64 * rhs.into().val as u64) % Self::modulus() as u64) as u32;
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> DivAssign<T> for StaticModInt<M> {
        fn div_assign(&mut self, rhs: T) {
            *self *= rhs.into().inv();
        }
    }

    macro_rules! impl_binnary_operators {
    ( $({ $op: ident, $op_assign: ident, $fn: ident, $fn_assign: ident}),* $(,)? ) => { $(
        impl<M: Modulus, T: Into<StaticModInt<M>>> std::ops::$op<T> for StaticModInt<M> {
            type Output = StaticModInt<M>;
            fn $fn(mut self, rhs: T) -> StaticModInt<M> {
                self.$fn_assign(rhs.into());
                self
            }
        }

        impl<M: Modulus> std::ops::$op<&StaticModInt<M>> for StaticModInt<M> {
            type Output = StaticModInt<M>;
            fn $fn(self, rhs: &StaticModInt<M>) -> StaticModInt<M> {
                self.$fn(*rhs)
            }
        }

        impl<M: Modulus, T: Into<StaticModInt<M>>> std::ops::$op<T> for &StaticModInt<M> {
            type Output = StaticModInt<M>;
            fn $fn(self, rhs: T) -> StaticModInt<M> {
                (*self).$fn(rhs.into())
            }
        }

        impl<M: Modulus> std::ops::$op<&StaticModInt<M>> for &StaticModInt<M> {
            type Output = StaticModInt<M>;
            fn $fn(self, rhs: &StaticModInt<M>) -> StaticModInt<M> {
                (*self).$fn(*rhs)
            }
        }

        impl<M: Modulus> std::ops::$op_assign<&StaticModInt<M>> for StaticModInt<M> {
            fn $fn_assign(&mut self, rhs: &StaticModInt<M>) {
                *self = self.$fn(*rhs);
            }
        }
    )* };
}

    impl_binnary_operators!(
        {Add, AddAssign, add, add_assign},
        {Sub, SubAssign, sub, sub_assign},
        {Mul, MulAssign, mul, mul_assign},
        {Div, DivAssign, div, div_assign},
    );

    impl<M: Modulus> std::iter::Sum for StaticModInt<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::raw(0), Add::add)
        }
    }

    impl<'a, M: Modulus> std::iter::Sum<&'a StaticModInt<M>> for StaticModInt<M> {
        fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::raw(0), Add::add)
        }
    }

    impl<M: Modulus> std::iter::Product for StaticModInt<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::raw(1), Mul::mul)
        }
    }

    impl<'a, M: Modulus> std::iter::Product<&'a StaticModInt<M>> for StaticModInt<M> {
        fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::raw(1), Mul::mul)
        }
    }

    pub type ModInt998244353 = StaticModInt<Mod998244353>;
    pub type ModInt1000000007 = StaticModInt<Mod1000000007>;
}
0