結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー elphe
提出日時 2026-01-11 16:04:28
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 1,363 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,885 ms
コンパイル使用メモリ 411,864 KB
実行使用メモリ 34,816 KB
最終ジャッジ日時 2026-01-11 16:05:03
合計ジャッジ時間 26,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{fastout, input, marker::Bytes};

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

    println!("{}", output(solve(c)))
}

fn solve(c: Vec<Vec<u8>>) -> u32 {
    let n = c.len();
    let mut dp = vec![vec![vec![0; n]; n]; n];
    if c[0][0] == c[n - 1][n - 1] {
        dp[0][0][n - 1] = 1;
    }
    for i in 0..(n - 1) {
        for j in 0..=i {
            for k in (n - 1 - i)..=(n - 1) {
                if c[j][i - j + 1] == c[k][(n - 1) - i + ((n - 1) - k) - 1] {
                    dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % 998244353;
                }
                if c[j + 1][i - j] == c[k][(n - 1) - i + ((n - 1) - k) - 1] {
                    dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k]) % 998244353;
                }
                if c[j][i - j + 1] == c[k - 1][(n - 1) - i + ((n - 1) - k)] {
                    dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % 998244353;
                }
                if c[j + 1][i - j] == c[k - 1][(n - 1) - i + ((n - 1) - k)] {
                    dp[i + 1][j + 1][k - 1] = (dp[i + 1][j + 1][k - 1] + dp[i][j][k]) % 998244353;
                }
            }
        }
    }
    (0..=(n - 1))
        .map(|i| dp[n - 1][i][i])
        .fold(0, |acc, x| (acc + x) % 998244353)
}

fn output(ans: u32) -> u32 {
    ans
}
0