题目来源：ACL Beginner Contest F – Heights and Pairs。

给定一个大小为 $2N$ 的数组 $H$ ，要求将 $H$ 中的元素两两匹配，使得恰好构成 $N$ 个数对 $(H_i,H_j)$ 满足 $H_i\neq H_j$ 。

$N\leq 50000, H_i\leq 100000$ 。

首先容易想到通过容斥原理来解决本题，也就是转化为：

+ 至少有0对相同数对的方案数
- 至少有1对相同数对的方案数
+ 至少有2对相同数对的方案数
- 至少有3对相同数对的方案数
+ ...

那么我们需要解决的问题就是：求解至少含有 $i$ 对相同数对的方案数 $f_i$ 。

先从最简单的情况开始考虑，也就是 $f_0$ 。此时通过思维或者找规律都可以发现答案就是 $(2N-1)!!$ ，也就是 $2N-1$ 的双阶乘 $1\times 3\times 5\times \cdots \times (2N-1)$ 。从组合意义上，我们可以给出一个简单的解释：对于数组中的第一个数而言，与它匹配的数有 $2N-1$ 种可能性；去掉这两个已匹配的数后，与此时数组中的第一个数匹配的数有 $2N-1-2$ 种可能……

利用上面的结论，再继续求解 $f_i$ 。由于数据范围中 $H_i\leq 10^5$ ，因此我们可以开一个大小为 $10^5$ 的桶存下所有数字，比如数组 $3,3,3,4,4,6$ 就是这样一个桶：$[0,0,0,3,2,0,1]$ 。这步转换将所有相同的数字划分到了同一类中，有利于进行后文中的多项式操作。

然后对于每一个桶，我们都可以对它单独求解一个子问题：假设一共 $2N$ 个元素，现在有 $M_i$ 个相同的元素 $i$ ，我们两两匹配得到的数对中至少有 $j$ 对 $(i,i)$ ，假设方案数为 $g_{i,j}$ ，求 $g_{i,j}(j\in [0,\frac{M_i}{2}])$ 。

这个答案不难推出是 $g_{i,j}=\binom{M_i}{2j}(2j-1)!!$ 。然后，不妨构造多项式组 $G$ ，其中 $G_i=g_{i,0}+g_{i,1}x+g_{i,2}x^2+\cdots + g_{i,\frac{M_i}{2}}x^{\frac{M_i}{2}}$ 。

从多项式的状态转移角度考虑，$f_i = [x^i](2i-1)!!\prod_{i=0}^{100000}G_i$ 。本题的答案就是 $\sum_{i=0}^{100000}(-1)^if_i$ 。

注意这个多项式连乘中，所有多项式的最高度数之和的量级是 $O(N)$ 的，因此我们可以通过启发式合并的方法，利用小根堆优先进行度数较低的多项式乘法以优化时间复杂度至 $O(N\log^2N)$ 。

AC代码。