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}\)。