#P17721. [2026年福建省队集训]理所当然

[2026年福建省队集训]理所当然

题目描述

小 ε\varepsilon 和小 ω\omega 是两个关系很好的女孩子,理所当然地,她们想要编织许多共同的回忆。

小 ω\omega 喜欢画画,因此,她理所当然地想要和小 ε\varepsilon 一起在一张 n×nn\times n 的网格图上作画。

理所当然地,画纸一开始是蓝色的,而小 ε\varepsilon 和小 ω\omega 想要将一些格子涂上绚丽的颜色。小 ε\varepsilon 拿着粉色的画笔,而小 ω\omega 拿着白色的画笔。

为了兼顾画面的美观性与简洁性,小 ε\varepsilon 想要在每行中选择 11 个格子涂上粉色,而小 ω\omega 想要在每行中选择 22 个格子涂上白色。由于颜色的重叠会使得图案显得杂乱,理所当然地,她们选择的格子需要两两不同。

作为一名优秀的画家,小 ω\omega 想要在创作的同时保持画面的平衡性。因此,她想要在绘画结束后,每列中的白色格子数量相同。

现在,小 ε\varepsilon 已经完成了画作前一部分的创作。对于任意 1≤i≤n1\le i\le n,她选择了第 ii 行的第 pi(1≤pi≤n)p_i(1\le p_i\le n) 个格子涂上了粉色。现在,小 ω\omega 理所当然地想要求出她有多少种上色方式完成画作的后半部分,使得最终的画作符合以上的所有要求。

由于答案可能很大,你只需要输出其对 998244353998244353 取模后的结果。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据:

  • 第一行一个正整数 nn,表示画布的尺寸;
  • 第二行 nn 个正整数 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n,其中第 ii 个整数 pi(1≤pi≤n)p_i(1\le p_i\le n) 表示第 ii 行中小 ε\varepsilon 染色过的格子所在列编号。

输出格式

对于每组测试数据,输出一行一个非负整数表示答案。

样例输入

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

样例输出

0
0
1
9

样例解释

该组样例中共包含 44 组测试数据。

  • 对于第 11 组和第 22 组测试数据,可以证明小 ω\omega 不存在符合条件的染色方案;
  • 对于第 33 组测试数据,唯一一种可能的方案为小 ω\omega 将 (1,2),(1,3),(2,1),(2,3),(3,1),(3,2)(1,2),(1,3),(2,1),(2,3),(3,1),(3,2) 所代表的格子染上颜色,其中 (x,y)(x,y) 代表位于第 xx 行第 yy 列的格子;
  • 对于第 44 组测试数据,一种可能的方案为小 ω\omega 选择 (1,1),(1,3),(2,1),(2,4),(3,2),(3,4),(4,2),(4,3)(1,1),(1,3),(2,1),(2,4),(3,2),(3,4),(4,2),(4,3) 这些格子染白。

数据范围与提示

对于所有测试数据:

  • 1≤T≤101\le T\le 10;
  • 1≤n≤5001\le n\le 500;
  • 对于任意 1≤i≤n1\le i\le n,1≤pi≤n1\le p_i\le n。

各测试点的具体限制见下表:

测试点编号 n≤n\le 特殊性质
1∼31\sim 3 88 无
4∼54\sim 5 1212
6∼76\sim 7 2020
88 5050
9∼109\sim 10 100100
11∼1211\sim 12 500500 A
13∼1513\sim 15 B
16∼1716\sim 17 C
18∼1918\sim 19 D
20∼2120\sim 21 300300 无
22∼2522\sim 25 500500

特殊性质 A:保证 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n 互不相同;

特殊性质 B:p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n 中不同数字的种类数不超过 88;

特殊性质 C:对于每个 1≤x≤n1\le x\le n,满足 pi=xp_i=x 的 i(1≤i≤n)i(1\le i\le n) 的个数不超过 22;

特殊性质 D:记 f(x)f(x) 为满足 pi=xp_i=x 的 ii 的数量,则满足 f(x)≥3f(x)\ge 3 的 x(1≤x≤n)x(1\le x\le n) 数量不超过 1010。