33OJ
登录 注册

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

    ID: 20434 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及 上传者: 标签>数学洛谷原创O2优化组合数学洛谷比赛

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

背景

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

题目描述

跑酷训练场可以视为一个无限延伸的实数轴,其中有 2n2n 个正整数位置(可以相同)被特殊标注,称为跳跃位点,这些位点的位置由一个正整数数列 AA 给定。

跑酷大神小 K 要在跑酷训练场上训练跳跃。具体地,在一次训练中,对于一个长为 2n2n 的跳跃位点数列 BB,小 K 会对所有奇数 ii 从 11 到 2n−12n-1 依次执行:

  • 从 bib_i 跳跃到 bi+1b_{i+1}。

显然,每次跳跃途经的位置形成一个实数轴上的区间。对于跳跃位点数列 BB 而言,其训练价值定义为本次训练的所有 nn 次跳跃形成的区间的交区间的长度(如果交区间不存在,那么长度为 00)。

为了帮助小 K 制定训练计划,请求出 AA 的所有 (2n)!(2n)! 种重新排列的训练价值的总和(可以证明这是一个整数)对 998244353998244353 取模后的结果。

注意:

这里的排列是对 AA 中的元素进行排列,而不是只对数值进行排列。 例如对于 A=(5,5) A=(5,5) ,虽然两个元素的数值相同,但仍有两种元素排列:

(a1,a2),(a2,a1).(a_1,a_2),\quad (a_2,a_1).

它们对应的排列 BB 分别为

(51,52),(52,51),(5_1,5_2),\quad (5_2,5_1),

下角标是为了区分这个 55 是原序列中第几个 55。

上面的这两种排列都需要计入答案。

输入格式

第一行输入一个整数 TT,表示测试数据的组数。

接下来对于每组测试数据:

  • 第一行输入一个整数 nn;
  • 第二行输入 2n2n 个整数 a1,a2,…,a2na_1,a_2,\ldots,a_{2n}。

输出格式

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

4
1
1 2
1
5 5
2
1 2 3 4
2
1 1 4 4
2
0
16
48

提示

【样例 1 解释】

对于第一组数据,只有两种情况:(1,2)(1,2) 或是 (2,1)(2,1),第一种情况是从 11 跳到 22,因为只有一个区间所以区间交就是本身,此时答案为 2−1=12-1 = 1;另一种情况同理,答案也为 11,所以最终总和为 1+1=21+1=2。

对于第二组数据,也只有两种情况,(51,52)(5_1,5_2) 或是 (52,51)(5_2,5_1),类似上面的过程,两个的答案都是 5−5=05-5=0,所以最终总和为 00。

对于第三组数据,一种情况是 (1,3,2,4)(1,3,2,4),两个跳跃的区间是 1→31\to 3 和 2→42\to 4,两个区间的交应当为 22 到 33 这一段,所以这个方案下答案是 3−2=13-2=1。因为情况数过多,所以只能告诉你这 4!4! 种情况总和是 1616。

对于第四组数据,我们暂时无法告诉你为什么答案是 4848。

【数据范围与约定】

本题采用捆绑测试。

对于所有测试数据,保证:

  • 1≤T≤2×1051\le T\le 2\times 10^5;
  • 1≤n≤2×1051\le n\le 2\times 10^5;
  • 1≤ai≤1091\le a_i\le 10^9;
  • 单个测试文件内 ∑n≤2×105\sum n\le 2\times 10^5。
Subtask 特殊限制 分值
1 ∑n≤5\sum n\le 5 2020
2 ∑n≤10\sum n\le 10
3 ∑n≤5000\sum n\le 5000
4 每组测试中的 AA 都是一个长度为 2n2n 的排列
5 无特殊限制