这是啥子题目的题解

题目链接。

1. 将答案转化为环的贡献

从 向 连边，显然每个点有一条入边和一条出边，每个点在且仅在一个环内，假设这个环长度为 ，显然需要 次交换，最小代价为环内元素最小值乘以剩下元素之和。

第二个结论证明如下：

设环内最小值为 ，则当前代价为 ，尝试微扰法证明，假设从 开始交换，则代价为：

由此，说明从 交换最优。

综上，得出式子：

（ 不枚举到 的原因是此时 是空集，可以去掉。）

2. 将环的贡献再次拆贡献转化式子

考虑钦定最小值 后的贡献，分别考虑环长为 （即 ）时的情况。

分别考虑 中每一个可能的 ，发现对于一个 有如下式子：

表示从 中去掉一个数 ，剩下的 个数从 中剩下的 个数中选出。

表示环内元素的排列方式， 表示环外元素的排列方式。

发现 可以提出来，剩下一个 就是 。

再对于每一个 求和，式子如下：

3. 化简式子

观察上面这一坨，发现 可以展开为 ，化简为

提出 ，剩下的 ，等于

现在再整理一下，式子变为：

再整理：

4. 计算内层和（还是化简式子）

考虑内层和 。

令 ，则上式变为

令 ，有 。

代入上式，得 。

发现 ，因此 ，化简为 。

提出 ，得 。

好的，化简完了，人也去了。

5. 代入外层，化简最终式子，计算答案

将内层和的结果代入外面（注意 ）：

你说得对，但是以下就是答案式子，可以 计算。

附录：朱世杰恒等式证明

朱世杰恒等式：对任意整数 和 ，有 。

证明：

使用数学归纳法。

1. 基例：当 时，左边为 ，右边为 ，成立。

2. 归纳假设：假设当 时，等式成立，即 。

3. 归纳步骤：需要证明当 时，等式也成立：
   

   根据归纳假设，右边可以写成：
   ，根据杨辉三角性质，有 。
   因此，等式在 时也成立。

综上所述，朱世杰恒等式对所有整数 都成立。