E Max-Min Sums
题面
给一个整数集合 $A$ , $\lvert A \rvert = n$ 和一个整数 $k$ .
求 :
$$\sum_{S \in A} [ \lvert S \rvert = k]\ f(s)$$
并对 $10^9 + 7$ 取模 .
其中 , $f(x) = \max_{x \in S} - \min_{x \in S}$
解题思路
最暴力的方法就是枚举 $C_n^k$ 元素个数为 $k$ 的子集 , 然后找 $\max$ 和 $\min$ , 复杂度爆炸 .
考虑集合的无序性 . 将集合中的元素从小到大排序 , 然后计算每个数可能子多少个子集中成为最大值 / 最小值 .
考虑如何统计作为子集中最大值的次数 :
对于前 $k - 1$ 个数 , 不可能成为任何子集的最大值 . 对于其它的数 , 第 $i$ 个数成为最大值的可能有 $C_{i - 1}^{k - 1}$ 种 , 即在前 $i - 1$ 个数中选 $k - 1$ 个数 , 与第 $i$ 个数构成子集 , 使其成为最大值 .
对于最小值 , 同理 .
记得用逆元 .