P17762 「奶龙OI」Round 3 - 跑酷大神

跑酷大神需要经历严苛的训练！

跑酷训练场可以视为一个无限延伸的实数轴，其中有 $2n$ 个正整数位置（可以相同）被特殊标注，称为**跳跃位点**，这些位点的位置由一个正整数数列 $A$ 给定。 跑酷大神小 K 要在跑酷训练场上训练跳跃。具体地，在一次**训练**中，对于一个长为 $2n$ 的跳跃位点数列 $B$，小 K 会对所有**奇数** $i$ 从 $1$ 到 $2n-1$ 依次执行： - 从 $b_i$ 跳跃到 $b_{i+1}$。 显然，每次跳跃途经的位置形成一个实数轴上的区间。对于跳跃位点数列 $B$ 而言，其**训练价值**定义为本次训练的所有 $n$ 次跳跃形成的区间的交区间的长度（如果交区间不存在，那么长度为 $0$）。 为了帮助小 K 制定训练计划，请求出 $A$ 的所有 $(2n)!$ 种重新排列的训练价值的总和（可以证明这是一个整数）对 $998244353$ 取模后的结果。 **注意**： 这里的排列是对 $A$ 中的元素进行排列，而不是只对数值进行排列。 例如对于 $ A=(5,5) $，虽然两个元素的数值相同，但仍有两种元素排列： $$ (a_1,a_2),\quad (a_2,a_1). $$ 它们对应的排列 $B$ 分别为 $$ (5_1,5_2),\quad (5_2,5_1), $$ 下角标是为了区分这个 $5$ 是原序列中第几个 $5$。 上面的这两种排列都需要计入答案。

第一行输入一个整数 $T$，表示测试数据的组数。 接下来对于每组测试数据： - 第一行输入一个整数 $n$； - 第二行输入 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$。

对于每组测试数据，输出一行一个整数，表示所有重排的训练价值之和对 $998244353$ 取模后的结果。

#### 【样例 1 解释】 对于第一组数据，只有两种情况：$(1,2)$ 或是 $(2,1)$，第一种情况是从 $1$ 跳到 $2$，因为只有一个区间所以区间交就是本身，此时答案为 $2-1 = 1$；另一种情况同理，答案也为 $1$，所以最终总和为 $1+1=2$。 对于第二组数据，也只有两种情况，$(5_1,5_2)$ 或是 $(5_2,5_1)$，类似上面的过程，两个的答案都是 $5-5=0$，所以最终总和为 $0$。 对于第三组数据，一种情况是 $(1,3,2,4)$，两个跳跃的区间是 $1\to 3$ 和 $2\to 4$，两个区间的交应当为 $2$ 到 $3$ 这一段，所以这个方案下答案是 $3-2=1$。因为情况数过多，所以只能告诉你这 $4!$ 种情况总和是 $16$。 对于第四组数据，我们暂时无法告诉你为什么答案是 $48$。 #### 【数据范围与约定】 **本题采用捆绑测试。** 对于所有测试数据，保证： - $1\le T\le 2\times 10^5$； - $1\le n\le 2\times 10^5$； - $1\le a_i\le 10^9$； - 单个测试文件内 $\sum n\le 2\times 10^5$。 | Subtask | 特殊限制 | 分值 | | :---: | :--- | :---: | | 1 | $\sum n\le 5$ | $20$ | | 2 | $\sum n\le 10$ | $20$ | | 3 | $\sum n\le 5000$ | $20$ | | 4 | 每组测试中的 $A$ 都是一个长度为 $2n$ 的排列 | $20$ | | 5 | 无特殊限制 | $20$ |