题意：给定一个长度为 $n$ 的序列，问有多少个重排序列的方案使得相邻两个数的和都 $\geq k$。$n\leq 2\times 10 ^ 5$，$a_i, k\leq 10 ^ 9$。
神仙构造 + 组合数学，只能复述题解了。
首先考虑如何生成这样的一个合法序列。考虑对序列排序，给定两个指针 $l, r$，使得 $[l, r]$ 里面的数都没有填入新的序列 $B$，其他的已经填入了。
我们分两种情况：如果 $A_l + A_r < k$，就将 $A_l$ 插入 $B$，否则 $A_r$ 插入 $B$。两边的指针相应移动。
首先容易发现的结论是 $A_l < \dfrac k2, A_r\geq \dfrac k2$。
假设 $A_l + A_r < k$ 即插入 $l$ 的话，我们需要考虑哪些位置可以插入。假设满足 $\max\{B_{i}, B_{i + 1}\} + A_l\geq k$ 的位置有 $s$ 个。
结论 1：满足 $\max\{B_i, B_{i + 1}\} + A_r\geq k$ 的数也恰好有 $s$ 个。
证明：假设 $A_l = \dfrac k2 - d(d > 0)$，那么 $A_r \geq \dfrac k2 + d$（注意我们现在需要插入 $r$，一定满足 $A_l + A_r\geq k$），如果 $B_i$ 和 $B_{i + 1}$ 中间存在一个数 $< \dfrac k2 - d$，那么不可能满足 $B_i + A_l \geq k$，同时也不满足 $B_i + A_r\geq k$（注意 $B_i$ 不可能等于 $A_l$，因为在插入第一个 $A_l$ 之前一定会先插入 $A_r$）。满足 $B_i + A_l\geq k$ 的一定满足 $B_i + A_r\geq k$，这个显然。
那么我们就证明到了不管是 $A_l$ 还是 $A_r$ 插入，都恰好有 $s$ 个可插入的位置。
结论 2：插入 $A_l$ 后会导致可插入位置 -1，插入 $A_r$ 后会导致可插入位置 +1。
首先证明除了插入位置外，其他位置的可插入性是不改变的。容易发现 $l$ 增加的话，一定是 $A_l + A_r < k$ 了，那么原来合法的一定还合法，由于不合法的时候一定存在一个 $B_i$ 使得 $B_i \leq A_l$，因为 $A_l + A_r < k$，所以不会再合法了。而如果 $r$ 减少的话，一定是满足 $A_l + A_r\geq k$，原来合法的一定还合法，原来不合法的一定满足 $B_i + A_r < k$，所以也永远不合法。
现在考虑插入位置附近。容易发现 $A_l$ 插入后两边不能再插入，因为 $A_l + A_r < k$ 了。而 $A_r$ 插入后两边都可以再插入，因为 $A_l + A_r \geq k$。
有了上面的结论，我们很容易写出第一部分代码：
1 | int main() |
下面我们来考虑和原问题的对应关系。
注意到我们现在相当于求的是整个 $B$ 的生成过程有多少种。我们暂且把它称为三角阵。现在我们需要知道的就是一个三角阵会对应多少个 $B$。
我们考虑从一个合法的序列 $B$ 删除来得到三角阵。容易发现我们只需要找到距离 $\dfrac k2$ 最近的值删除一个即可（如果存在两个值距离相同，显然选大的）。注意到这和三角阵的生成过程恰好是逆序的。
注意到一个合法的 $B$ 每次删除值的时候值都是一定的，主要在于删除哪一个值。显然单次会删除 $cnt$ 个中的一个，然后 cnt --。
那么我们就是需要将刚刚得到的答案除以所有数字出现次数的逆元即可。时间复杂度 $O(n\log n)$。
1 | int main() |