CF2038F

标签：frac min max sum CF2038F 序列 binom

\(\max(\min\{v\},\min\{r\})\) 太难看了！！！
运用经典 trick: \(\max(a,b)=a+b-\min(a,b)\)，可得:

\[\max(\min\{v\},\min\{r\})=\min\{v\}+\min\{r\}-\min(\min\{v\},\min\{r\}) \]

我们设 \(a_i=\min(v_i,r_i)\)，式子变成 \(\min\{v\}+\min\{r\}-\min\{a\}\)，这是三个相同的子问题。

现在问题转化为对一个序列求出所有大小为 \(k\) 的子集的最小值之和，设其为 \(f(k)\)。
首先答案与序列的顺序无关，所以先把序列从小到大排序。然后钦定 \(a_i\) 为集合最小值，我们要从其后面 \(n_i\) 个数中
选 \(k-1\) 个，那么其贡献为 \(a_i\times\binom{n-i}{k-1}\)，即 \(f(k)=\sum\limits_{i=1}^{n-k+1}a_i\binom{n-i}{k-1}\)。

现在我们对 \(1\sim n\) 中的每个 \(k\) 都求一遍答案，时间复杂度为 \(O(n^2)\)，不能接受。
简单化一下式子，把组合数拆开：

\[f(k)=\frac{1}{(k-1)!}\left(\sum\limits_{i=1}^{n-k+1}a_i(n-i)!\times\frac{1}{(n-i-k+1)!}\right) \]

发现这个东西是卷积的形式，我们定义数组 \(F\) 满足 \(F_i=a_i(n-i)!\)，\(G\) 满足 \(G_i=\frac{1}{i!}\)，将两个数组卷积之后基本就能得到我们需要的答案了，我们现在求的是所有方案的总和，最后除以一个方案数即可。

标签：frac,min,max,sum,CF2038F,序列,binom
From： https://www.cnblogs.com/ZepX-D/p/18554754