← 返回题目列表

Codeforces · 2150/B

B. 网格计数

中文机器翻译题面 查看原题
ParagonX9 - HyperioxX
⠀

Alice 有一个大小为 $$$n \times n$$$ 的网格。最初,所有细胞都是白色的。 Alice 想要将一些单元格染成黑色以满足某些属性。

设 $$$(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$$$ 为黑色单元格。给定一个大小为 $$$n$$$ 的数组 $$$a$$$。必须满足以下条件:

  • 对于每一行 $$$k$$$ ($$$1 \le k \le n$$$),恰好存在 $$$a_k$$$ 索引 $$$i$$$ ($$$1 \le i \le m$$$) 使得 $$$x_i = k$$$。不太正式,$$$k$$$ 行中应该有 $$$a_k$$$ 黑色单元格。
  • 对于每个 $$$k$$$ ($$$1 \le k \le n$$$),存在一个索引 $$$i$$$ 使得 $$$\max(x_i, y_i) = k$$$。
  • 对于每个 $$$k$$$ ($$$1 \le k \le n$$$),存在一个索引 $$$i$$$ 使得 $$$\max(x_i, n + 1 - y_i) = k$$$。

例如,当 $$$a = [2, 2, 1, 0, 0]$$$ 时,一组可能的黑色单元格为 $$$\{(1, 1), (2, 2), (3, 3), (2, 4), (1, 5)\}$$$。这对应于以下网格:

5×5 网格,具有指定的黑色单元格。

计算可能的网格数。如果某个网格中某个单元格的颜色为黑色,而另一个网格中的单元格为白色,则 $$$2$$$ 网格被认为是不同的。由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 — $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含一个整数:有效网格的数量以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

5
5
2 2 1 0 0
2
2 0
2
1 1
4
3 1 0 0
4
0 0 0 0

输出
复制

1
1
0
2
0

注意

在第一个测试用例中,唯一有效的网格是语句中的网格。

在第二个测试用例中,唯一有效的网格由黑色单元格 $$$\{(1, 1), (1, 2)\}$$$ 描述。

在第三个测试用例中,没有有效的网格。