← 返回题目列表

AtCoder · abc259_h

Ex. 另一种路径计数

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个正方形网格 N 行垂直排列并且 N 列水平排列。广场位于 i从顶部开始的第行和 j从左边算起的第列有一个整数标签 a_{i,j}.
考虑从一个方格开始并继续前进所获得的路径 向右或向下 到相邻方块零次或多次。求模数 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)