自动搬运

查看原文

来自洛谷，原作者为

	zhangzirui66 不拿7勾不改签|CF不上蓝不改签|AT不上绿不改签|最后在线时间：2025年8月24日22时23分

搬运于2025-08-24 22:23:24，当前版本为作者最后更新于2024-06-15 10:19:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于和最值有关，可以先升序排序。排序后对于每个数 $a_i$，没有哪个数 $a_j$ 满足 $j<i$，$a_j \ge a_i$

对于每个数 $a_i$，会贡献 $C^{k-1}_{j-1}$ 次，因为我们要在前 $i$ 个数中选 $k$ 个数，由于 $a_i$ 必须选，也就是在前 $i-1$ 个数中选 $k-1$ 个数。

每次贡献的值？显然是 $a_i$ 所以单个 $a_i$ 的贡献值为

总答案为

关于组合数，可以用递推法求出。

Code:

#include<bits/stdc++.h>
using namespace std;
int n, k, ans, a[100005], c[100005][55];
int main(){
	cin >> n >> k;
	c[0][0] = 1;
	for(int i = 1; i <= n; i ++){
		c[i][0] = 1;
		for(int j = 1; j <= min(i, k); j ++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % 1000000007;//最多只有C[n][k]，取个min值
	}
	for(int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i = k; i <= n; i ++) ans = (ans +(1ll * c[i - 1][k - 1] * a[i] % 1000000007)) % 1000000007;
	printf("%d", ans);
	return 0;
}