結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー NaH54i
提出日時 2026-01-11 20:57:00
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,025 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,007 ms
コンパイル使用メモリ 346,684 KB
実行使用メモリ 67,712 KB
最終ジャッジ日時 2026-01-11 20:57:06
合計ジャッジ時間 5,270 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 RE * 1
other RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
using ll = long long;
using ld = long double;
//using mint = modint998244353;
int main(){
    ll n;
    cin >> n;
    vector<string> s(n);

    for(ll i = 0; i < n; i++){
        cin >> s[i];
    }

    vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(n,vector<ll>(n,0)));

    for(ll i = 0; i < n; i++){
        dp[i][n-i-1][i] = 1;
    }
    
    for(ll i = n-1; i > 0; i--){
        for(ll t = 0; t < i; t++){
            ll x = i - t;
            ll y = t;
            ll xx = x;
            ll yy = y;

            xx--;
            for(ll u = 0; u < n; u++){
                ll xd = u;
                ll yd = n-i-u;
                xd++;
                if(xd < n && yd < n){
                    if(s[xx][yy] == s[xd][yd]){
                        dp[xx][yy][xd] += dp[x][y][u];
                        dp[xx][yy][xd] %= 998244353;
                    }
                }
                xd--;
                yd++;
                if(xd < n && yd < n){
                    if(s[xx][yy] == s[xd][yd]){
                        dp[xx][yy][xd] += dp[x][y][u];
                        dp[xx][yy][xd] %= 998244353;
                    }
                }
            }

            xx++;
            yy--;
            for(ll u = 0; u < n; u++){
                ll xd = u;
                ll yd = n-i-u;
                xd++;
                if(xd < n && yd < n){
                    if(s[xx][yy] == s[xd][yd]){
                        dp[xx][yy][xd] += dp[x][y][u];
                        dp[xx][yy][xd] %= 998244353;
                    }
                }
                xd--;
                yd++;
                if(xd < n && yd < n){
                    if(s[xx][yy] == s[xd][yd]){
                        dp[xx][yy][xd] += dp[x][y][u];
                        dp[xx][yy][xd] %= 998244353;
                    }
                }
            }
        }
    }

    
    cout << dp[0][0][0] << '\n';


    return 0;
}
0