No.3429 Palindromic Path (Hard)
タグ : / 解いたユーザー数 44
作問者 :
まみめ
/ テスター :
hirayuu_yc
harel
rogi52
遭難者
syndrome
kidodesu
👑 
ArcAki
Eku
※この問題は Palindromic Path (Easy) の制約が異なる問題です。
問題文
$N×N$ のマス目からなるグリッドがあります。各マス $(i,j)\space (1 \leq i,j \leq N)$ には英小文字 $c_{i,j}$ が書かれています。
左上隅のマス $(1,1)$ からスタートし、右または下への移動のみを繰り返して、右下隅のマス $(N,N)$ のゴールへ移動します。
このとき、通過した $2N-1$ 個のマス（スタートとゴールを含む）に書かれた文字を順に読んだ文字列を $S$ とします。
マス $(1,1)$ から $(N,N)$ への経路のうち、文字列 $S$ が回文であるものは何通りありますか。
ただし、長さ $M$ の文字列 $T$ が回文であるとは、任意の $1 \leq i \leq M$ について、$T$ の $i$ 文字目と $(M+1-i)$ 文字目が一致していることをいいます。
答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを出力してください。
入力
- $2 \leq N \leq 200$
- $c_{i,j}$ は英小文字
$N$
$c_{1,1}c_{1,2}...c_{1,N}$
$c_{2,1}c_{2,2}...c_{2,N}$
$\vdots$
$c_{N,1}c_{N,2}...c_{N,N}$
出力
回文となるような経路の総数を $998244353$ で割った余りを出力してください。。
サンプル
サンプル1
入力
3 aba aba aba
出力
2
$N=3$ のため、$(1,1)$ から $(3,3)$ への移動方法は $6$ 通りあります。
$(1,1)→(1,2)→(1,3)→(2,3)→(3,3)$ : abaaa (回文ではない)
$(1,1)→(1,2)→(2,2)→(2,3)→(3,3)$ : abbaa (回文ではない)
$(1,1)→(1,2)→(2,2)→(3,2)→(3,3)$ : abbba (回文)
$(1,1)→(2,1)→(2,2)→(2,3)→(3,3)$ : aabaa (回文)
$(1,1)→(2,1)→(2,2)→(3,2)→(3,3)$ : aabba (回文ではない)
$(1,1)→(2,1)→(3,1)→(3,2)→(3,3)$ : aaaba (回文ではない)
回文となる経路は $2$ 通りです。
サンプル2
入力
3 ynu cpc con
出力
0
どんな経路でも $S$ が回文にならないため $0$ を出力します。
サンプル3
入力
18 aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa
出力
337117514
答えを $998244353$ で割った余りを出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。