1009. 价值总是越大越好

题目描述

给定一个长度为 $2N$ 的数组 $P$。数组中的非零元素互不相同，值域为 $1$ 到 $2N$；缺失的元素使用 $0$ 表示。

你需要将所有 $0$ 替换为尚未出现的整数，使最终的 $P$ 成为 $1$ 到 $2N$ 的一个排列。

定义排列的价值为

$|P_1-P_2|+|P_3-P_4|+\cdots+|P_{2N-1}-P_{2N}|$。

求有多少种补全方式能够使这个价值最大。答案对 $998244353$ 取模。

两个补全后的数组只要至少有一个位置不同，就视为不同的补全方式。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据包含两行：

第一行输入一个整数 $N$，表示数组长度为 $2N$。

第二行输入 $2N$ 个整数 $P_1,P_2,\ldots,P_{2N}$。其中 $0$ 表示该位置尚未填入数字。

对于一组测试数据：

$1\le N\le 2\times 10^5$；

$0\le P_i\le 2N$；

所有非零的 $P_i$ 互不相同。

OJ 中只有一个正式测试点，该测试点满足：

$T=10000$；

$\sum N=10^6$。

输出格式

对于每组测试数据输出一行，表示使排列价值最大的补全方式数量，对 $998244353$ 取模后的结果。

样例输入

3
4
3 0 0 5 6 8 0 4
2
0 0 0 0
3
4 6 1 5 3 2

样例输出

2
16
1

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1009