AT_abc259_h [ABC259Ex] Yet Another Path Counting

题目描述

有一个纵向 $N$ 行横向 $N$ 列的网格，从上往下第 $i$ 行，从左往右第 $j$ 列的格子上标有整数标签 $a_{i,j}$。 你可以从任意一个格子出发，重复进行向右或向下移动到相邻格子的操作 $0$ 次或多次，得到一条路径。 请你求出所有起点和终点标签相同的路径的数量，并对 $998244353$ 取模。 注意，如果两条路径经过的格子集合（包括起点和终点）不同，则认为它们是不同的路径。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
1 3
3 1

输出 #1

6

说明/提示

限制条件

• $1 \leq N \leq 400$
• $1 \leq a_{i,j} \leq N^2$
• 输入均为整数

样例解释 1

满足条件的路径共有 $6$ 条。（用 $(i,j)$ 表示上第 $i$ 行、左第 $j$ 列的格子，下面依次给出每条路径经过的格子）

• $(1,1)$
• $(1,1) \to (1,2) \to (2,2)$
• $(1,1) \to (2,1) \to (2,2)$
• $(1,2)$
• $(2,1)$
• $(2,2)$

由 ChatGPT 4.1 翻译