102597: [AtCoder]ABC259 Ex - Yet Another Path Counting

Problem Statement

We have a grid of squares with $N$ rows arranged vertically and $N$ columns arranged horizontally. The square at the $i$-th row from the top and $j$-th column from the left has an integer label $a_{i,j}$.
Consider paths obtained by starting on one of the squares and going right or down to an adjacent square zero or more times. Find the number, modulo $998244353$, of such paths that start and end on squares with the same label.
Two paths are distinguished when they visit different sets of squares (including the starting and ending squares).

Constraints

• $1 \leq N \leq 400$
• $1 \leq a_{i,j} \leq N^2$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$a_{1,1}$ $\ldots$ $a_{1,N}$
$\vdots$
$a_{N,1}$ $\ldots$ $a_{N,N}$

Output

Print the answer.

Sample Input 1

2
1 3
3 1

Sample Output 1

6

The following six paths satisfy the requirements. ($(i, j)$ denotes the square at the $i$-th row from the top and $j$-th column from the left. Each path is represented as a sequence of squares it visits.)

• $(1,1)$
• $(1,1)$ → $(1,2)$ → $(2,2)$
• $(1,1)$ → $(2,1)$ → $(2,2)$
• $(1,2)$
• $(2,1)$
• $(2,2)$

问题描述

我们有一个网格，垂直排列有N行，水平排列有N列。从顶部数第i行、从左数第j列的方格标有一个整数标签$a_{i,j}$。
考虑从一个方格开始，向右或向下走0次或多次到达相邻方格的路径。找出以相同标签的方格开始和结束的路径的数量，对998244353取模。
当它们访问的方格集（包括起始和结束方格）不同时，两条路径被认为是不同的。

约束

• $1 \leq N \leq 400$
• $1 \leq a_{i,j} \leq N^2$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出以下格式：

$N$
$a_{1,1}$ $\ldots$ $a_{1,N}$
$\vdots$
$a_{N,1}$ $\ldots$ $a_{N,N}$

输出

打印答案。

样例输入1

2
1 3
3 1

样例输出1

6

以下六条路径满足要求。 ($(i, j)$表示从顶部数第i行、从左数第j列的方格。每条路径都表示为它访问的方格的序列。)

• $(1,1)$
• $(1,1)$ → $(1,2)$ → $(2,2)$
• $(1,1)$ → $(2,1)$ → $(2,2)$
• $(1,2)$
• $(2,1)$
• $(2,2)$