比赛 ZLXSCDay1 评测结果 AAAAAAAAAA
题目名称 PERICA 最终得分 100
用户昵称 铁策 运行时间 0.372 s
代码语言 C++ 内存使用 0.70 MiB
提交时间 2016-03-18 18:50:54
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int n, k;
int x[100010];
int gcd(long long x, long long y)
{
	return (y ? gcd(y, x % y) : x);
}
void ex_gcd(long long a, long long b, long long &x, long long &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return;
	}
	long long x1, y1;
	ex_gcd(b, a % b, x1, y1);
	x = y1,y = x1 - (a / b) * y1;
}
inline long long getrev(long long a, long long mod)
{
	if (!a || gcd(a, mod) > 1)
		return -1;
	long long x, y;
	ex_gcd(a, mod, x, y);
	return (x + mod) % mod;
}
int main()
{
	freopen("perica.in", "r", stdin);
	freopen("perica.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &x[i]);
	sort(x, x + n);
	long long now = 1, ans = x[k - 1];
	for (int i = k; i < n; i++)
	{
		long long t = getrev(i - k + 1, MOD);
		now = (now * t) % MOD;
		now = (now * i) % MOD;
		ans = (ans + x[i] * now) % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}