← 返回题目列表

Codeforces · 2122/E

E. 贪心网格计数

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

网格中的路径称为 贪婪 如果它从左上角单元格开始并且仅向右或向下移动,则始终移动到具有较大值的邻居(或者如果值相等)。

的 值 路径的 是其访问的单元格值的总和,包括起点和终点。

给定一个部分填充的 $$$2 \times n$$$ 介于 $$$1$$$ 和 $$$k$$$ 之间的整数网格,计算填充空单元格的方法数量,使得 每个子网格中的 在每个子网格中$$$^{\text{*}}$$$,存在一条贪婪路径,可以在所有向下/向右路径中获得最大值。由于答案可能很大,请以 $$$998\,244\,353$$$ 为模进行计算。

$$$^{\text{*}}$$$ $$$2 \times n$$$ 网格的子网格 $$$a_{i,j}$$$ 是由所有单元 $$$a_{x,y}$$$ 组成的网格,使得 $$$l_x \leq x \leq r_x$$$, $$$l_y \leq y \leq r_y$$$对于一些$$$1 \leq l_x \leq r_x \leq 2$$$,$$$1 \leq l_y \leq r_y \leq n$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 500$$$) - 分别是网格中的列数和整数范围。

接下来是两行,第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$-1 \leq a_{i,j} \leq k$$$, $$$a_{i,j} \neq 0$$$) —网格第 $$$i$$$ 行中单元格的值,其中 $$$-1$$$ 表示空单元格。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。

输出

对于每个测试用例,输出一个整数 - 满足上述条件的填充网格的方式数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

3
4 3
2 1 -1 2
2 -1 1 3
5 4
1 3 -1 4 2
-1 3 4 2 -1
10 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出
复制

6
64
123782927

注意

第一个测试用例中,满足条件的网格为: $$\begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix}.$$

在第二个测试用例中,所有填充网格的方式都满足条件。