CF2150B.Grid Counting

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)\}$。对应的网格如下：

在给定黑色格子的条件下，统计可能的网格的方案数。只要存在某个格子在两个网格中黑白色不同，则认为两个网格不同。由于答案可能很大，请输出对 $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$ 取模。

• 第一个测试用例中，只有题目所示的那一种涂黑方案。
• 第二个测试用例中，唯一的合法方案为 $\{(1,1), (1,2)\}$。
• 第三个测试用例中，没有合法方案。

由 ChatGPT 5 翻译