ARC145C 题解

problem & blog。

小清新结论题。

提供一个不需要脑子就可以 AC 的方法：看样例解释，猜到一定是 \((1,2)(3,4)\) 这样子，于是暴力，把前几项输进 OEIS 里，做完了。

显然取 \(\forall |A_i-B_i|=1\) 最优。

证明：对于 \(x-3,x-2,x-1,x\)，配对：
\((x-3,x-2)(x-1,x)\) 的贡献为 \((x-3)(x-2)+(x-1)x=2x^2-6x+6\)。
\((x-3,x)(x-2,x-1)\) 的贡献为 \((x-3)x+(x-2)(x-1)=2x^2-6x+2\)。
显然前者更优，同理容易归纳证明。

简单计数。

• 交换 \((A_i,B_i)\) 与 \((A_j,B_j)\) 仍然最优，方案数 \(n!\)。
• 交换 \(A_i\) 与 \(B_i\) 仍然最优，方案数 \(2^n\)。
• 去掉上述情况后考虑的是 \(\forall (A_i,B_i)=(2k-1,2k)\) 的问题。
• 不妨设同一对中，先出现的为 \(\alpha\)，后出现的为 \(\beta\)，则这个序列合法，当且仅当任意时刻，\(\alpha\) 的数量 \(\ge \beta\) 的数量。
• 此即卡特兰数 \(\dfrac1{n+1}\cdot\begin{pmatrix}2n\\n\end{pmatrix}\)。总答案即这些东西相乘。

code，时间复杂度 \(O(n)\)。