简单的组合问题，无序对

Question

题目描述

数学组合学问题

题目来源及自己的思路

竞争性节目

你期待的结果是什么？实际看到的错误信息又是什么？

我尝试了一种在O（n）中解决这个问题的方法。 但得到错误的答案。

我用2n！/（n！* 2 ^ n）

显然，所有人都希望自己队友的能力值尽可能高。我们称一个组队方案（即 N/2 个无序二元
组）为合法的，当且仅当不存在两支队伍 (A, B) 和 (C, D) 满足 SD > SB 且 SA > SC。在这种情
况下，A 和 D 会想要组队。
请求出有多少合法的组队方案。由于答案可能很大，请输出其对 1, 000, 000, 007 取模的结果。
输入格式
输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含一个整数 N。第二行包含 N 个整数 S1, S2, . . . , SN。
输出格式
对于每组数据，输出一行，包含一个整数，代表合法方案数对 1, 000, 000, 007 取模的结果。
数据范围
• 1 ≤ T ≤ 1, 000
• 2 ≤ N ≤ 105
• N 为偶数
•
∑N ≤ 106
• 1 ≤ Si ≤ 106
样例数据
输入
2
4
1 7 3 8
4
2 3 2 2