#P17762. 「奶龙OI」Round 3 - 跑酷大神
「奶龙OI」Round 3 - 跑酷大神
背景
跑酷大神需要经历严苛的训练!
题目描述
跑酷训练场可以视为一个无限延伸的实数轴,其中有 个正整数位置(可以相同)被特殊标注,称为跳跃位点,这些位点的位置由一个正整数数列 给定。
跑酷大神小 K 要在跑酷训练场上训练跳跃。具体地,在一次训练中,对于一个长为 的跳跃位点数列 ,小 K 会对所有奇数 从 到 依次执行:
- 从 跳跃到 。
显然,每次跳跃途经的位置形成一个实数轴上的区间。对于跳跃位点数列 而言,其训练价值定义为本次训练的所有 次跳跃形成的区间的交区间的长度(如果交区间不存在,那么长度为 )。
为了帮助小 K 制定训练计划,请求出 的所有 种重新排列的训练价值的总和(可以证明这是一个整数)对 取模后的结果。
注意:
这里的排列是对 中的元素进行排列,而不是只对数值进行排列。 例如对于 ,虽然两个元素的数值相同,但仍有两种元素排列:
它们对应的排列 分别为
下角标是为了区分这个 是原序列中第几个 。
上面的这两种排列都需要计入答案。
输入格式
第一行输入一个整数 ,表示测试数据的组数。
接下来对于每组测试数据:
- 第一行输入一个整数 ;
- 第二行输入 个整数 。
输出格式
对于每组测试数据,输出一行一个整数,表示所有重排的训练价值之和对 取模后的结果。
4
1
1 2
1
5 5
2
1 2 3 4
2
1 1 4 4
2
0
16
48
提示
【样例 1 解释】
对于第一组数据,只有两种情况: 或是 ,第一种情况是从 跳到 ,因为只有一个区间所以区间交就是本身,此时答案为 ;另一种情况同理,答案也为 ,所以最终总和为 。
对于第二组数据,也只有两种情况, 或是 ,类似上面的过程,两个的答案都是 ,所以最终总和为 。
对于第三组数据,一种情况是 ,两个跳跃的区间是 和 ,两个区间的交应当为 到 这一段,所以这个方案下答案是 。因为情况数过多,所以只能告诉你这 种情况总和是 。
对于第四组数据,我们暂时无法告诉你为什么答案是 。
【数据范围与约定】
本题采用捆绑测试。
对于所有测试数据,保证:
- ;
- ;
- ;
- 单个测试文件内 。
| Subtask | 特殊限制 | 分值 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | 每组测试中的 都是一个长度为 的排列 | |
| 5 | 无特殊限制 |