No.3429 Palindromic Path (Hard)
まみめ
hirayuu_yc
harel
rogi52
syndrome
kidodesu
ArcAki
Eku※This problem is Palindromic Path (Easy) with different constraints.
Problem Statement
There is a grid consisting of $N×N$ cells. Each cell $(i,j)\space (1 \leq i,j \leq N)$ contains a lowercase English letter $c_{i,j}$.
Starting from the top-left cell $(1,1)$, you move to the goal at the bottom-right cell $(N,N)$ by repeatedly moving only right or down.
Let $S$ be the string obtained by reading, in order, the characters written on the $2N-1$ cells passed through (including the start and the goal).
Among the paths from cell $(1,1)$ to $(N,N)$, how many are there for which the string $S$ is a palindrome?
Here, a string $T$ of length $M$ is called a palindrome if, for every $1 \leq i \leq M$, the $i$-th and $(M+1-i)$-th characters of $T$ are equal.
Since the answer can be very large, output it modulo $998244353$.
Input
- $2 \leq N \leq 200$
- $c_{i,j}$ is a lowercase English letter
$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}$
Output
Output the total number of paths that form a palindrome, modulo $998244353$.
Sample
Sample 1
Input
3 aba aba aba
Output
2
Since $N=3$, there are $6$ ways to move from $(1,1)$ to $(3,3)$.
$(1,1)→(1,2)→(1,3)→(2,3)→(3,3)$ : abaaa (not a palindrome)
$(1,1)→(1,2)→(2,2)→(2,3)→(3,3)$ : abbaa (not a palindrome)
$(1,1)→(1,2)→(2,2)→(3,2)→(3,3)$ : abbba (palindrome)
$(1,1)→(2,1)→(2,2)→(2,3)→(3,3)$ : aabaa (palindrome)
$(1,1)→(2,1)→(2,2)→(3,2)→(3,3)$ : aabba (not a palindrome)
$(1,1)→(2,1)→(3,1)→(3,2)→(3,3)$ : aaaba (not a palindrome)
There are $2$ paths that form a palindrome.
Sample 2
Input
3 ynu cpc con
Output
0
For every path, $S$ is not a palindrome, so output $0$.
Sample 3
Input
18 aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaa
Output
337117514
Note that you must output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。