Score : $600$ points

问题描述

我们有一个由 $N$ 行垂直排列和 $N$ 列水平排列的正方形网格。从上到下第 $i$ 行、从左到右第 $j$ 列的正方形有一个整数标签 $a_{i,j}$。

考虑这样的一类路径：从任意一个正方形出发，并且可以 向右或向下 零次或多次移动到相邻的正方形上。求满足起点和终点具有相同标签的此类路径的数量，结果对 $998244353$ 取模。

当两条路径访问了不同的正方形集合（包括起点和终点正方形）时，我们认为这两条路径是不同的。

以上为通义千问 qwen-max 翻译，仅供参考。

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)$

update @ 2024/3/10 11:00:40