ARC167

A.

题目明示，让每组的和尽可能平均就是平衡。

那相当于 \(a\) 升序排序后，前 \(2(n-m)\) 个数首尾配对成组，其余数单独成组即可。

题解有一个值得借鉴的技巧，补 \(0\) 使得 \(a\) 长度为 \(2m\)。

\(\color{green}{\checkmark}\)。

B.

记 \(S=\prod\limits_{d|A^B}d\)。

考虑素数 \(p|A\)，不妨设 \(p^q || A\)。

考虑计算 \(S\) 中有几个 \(p\)：\(cnt_p=\frac{(Bq+1)qB\varphi(\frac{A^B}{p^{qB}})}{2}\)。

那么 \(S\) 中 \(A\) 的次数：\(f_p = \lfloor\frac{cnt_p}{q}\rfloor\)。

那么答案即为 \(\min\limits_{p|A}f_p\)。

只需求解 \(f\) 即可。

注意到 \(f_p = \lfloor\frac{(Bq+1)q\varphi(\frac{A^B}{p^{qB}})}2\rfloor\)，\(\varphi(\frac{A^B}{p^{qB}})\) 可以通过处理 \(p\) 的次数得到，分母的 \(2\) 只需考察分子的每个因数是否存在一个偶数即可。

如果实现不好要开 __in128。

\(\color{green}{\checkmark}\)。

C. \(\color{#DB7D74}{\star}\)

真不会数数。

先拆贡献，枚举 \(a_i\)，考虑边权为 \(a_i\) 的边在 MST 中总共出现了几次（下文简称出现了几次）。

我们考虑 Kruskal 算法如何求解 MST：按边权从小到大考虑是否加入每一条边，一条边在 MST 中等价于加入此边后仍不存在环。

一个巧妙且关键的思考角度：对于排列 \(p\) 生成的图，边权为 \(w\) 的边的出现次数等于加入权为 \(w\) 的边之前的连通块个数和加入之后的作差。
这个角度有点像：一次操作的影响相当于操作之前和之后的差异。

如果将 \(a\) 升序排列，我们能设 \(f_i\) 表示对于所有排列，只考虑边权 \(\le a_i\) 的边时，能同时选出的边的最大数量（即连通块个数 \(-1\)）。
答案就是 \(\sum\limits_{i=2}^n a_i (f_i - f_{i-1})\)。

只需快速求解 \(f\)。

不妨设我们将要求解 \(f_m\)。

由于 \(a\) 已被我们升序排列，在排列中所有 \(>m\) 的元素我们都不用考虑了，直接变为 \((n-m)!\) 的系数。

把排列 \(p\) 中 \(\le m\) 的元素的下标拎出来，按升序记为序列 \(q\)。
那么 \(q\) 中两元素之差 \(\le k\) 等价于有连边，我们要选出尽可能多的边且不构成环。

另一个关键：我们用贪心思想处理最大化的限制。

贪心地，我们选取的边一定是 \(q\) 中两相邻元素构成的，否则一定不优。
而且，如果两相邻元素构成的边存在我们一定会选上。
可以证明这是最优策略。

那直接算次数：考虑 \((q_i,q_{i+1})\) 这条边什么时候被选。
只需让 \(q_{i+1}-q_i \le k\)。
将 \([q_i,q_{i+1}]\) 的数捆成一个数，枚举其长度 \(d \le k+1\)，相当于 \(m-1\) 个数在 \(n-(d-1)\) 个值域上的洞中随便选，即 \(\sum\limits_{d=2}^{k+1} \binom{n-(d-1)}{m-1} = \sum \limits_{d=1}^k\binom{n-d}{m-1}\)。

有 \(m-1\) 个 \((q_i,q_{i+1})\)。
\(q\) 序列下标映射到 \(p\) 序列的元素值上还有 \(m!\)。

所以 \(f_m=(m-1)m!(n-m)!\sum\limits_{d=1}^k\binom{n-d}{m-1}\)。

直接计算即可，复杂度 \(\mathcal{O(nk)}\)。

\(\color{green}{\checkmark}\)。

D. \(\color{#DB7D74}{\star}\)

考虑置换环，那么当且仅当只有一个置换环时合法。

考虑交换操作相当于什么：交换两个不在同一个环的数相当于合并这两个环。

我们考虑从小到大确定每个 \(i\) 的最终位置。

考虑已经确定 \(1 \sim i-1\) 的位置，现在要确定 \(i\) 的最终位置。

如果 \(i\) 已与 \(1\) 在同一个置换环中，由于步数最小，\(i\) 就不需要交换，保持原位。

否则，我们要在与 \(1\) 在同一置换环中，满足元素值 \(>i\) 的情况下，下标最小的那个元素交换。

特别地，如果元素值均 \(<i\)，我们选取最后那个，即 \(p_{i-1}\) 进行交换。

拿一个指针 \(j\) 从 \(1\) 开始扫，如果当前 \(p_j>i\) 或者 \(j = i - 1\)，那么就进行交换。

复杂度 \(\mathcal{O(n)}\)。

\(\color{green}{\checkmark}\)。

E. \(\color{#DB7D74}{\star}\)

真的不会构造。

不妨设其中一个顶点在 \((0,0)\)，所有顶点落在 \(I\) 和坐标轴上。

偶数是简单的，直接取 \((2,0)\)，和 \((\frac S2,\frac S2)\) 即可。

此处要求 \(S>2\)。

手玩一下，\(S=2\) 无解。

考虑奇数。

先把面积公式写出来：\(S=|x_1y_2-x_2y_1|\)。

由奇偶性分析，和偶数的构造，不难猜到令 \((x_1,y_1)=(3,1)\)，推出 \((x_2,y_2)=(\frac{S-3}2,\frac{S-1}2)\)。

但是这个构造要求 \(S\le 9\)。

大胆猜测 / 写个爆搜，\(S=1,3,5,7\) 无解。

\(\color{green}{\checkmark}\)。

F.

咕咕咕。