TLE了!为什么嗷

Cascol edited 4 年,9 月前

为什么这题我会TLE..

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <queue>
#include<string>
#include<string.h>
#include <vector>
#include <cstdio>
#include<map>
#include<cmath>
#include<unordered_map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod = 1e9 + 7, maxN = 1e6 + 5;
int n, m, T, a[maxN];
struct node
{
	int value, cnt;
};
vector<node> b;
inline int getint() {
	int num = 0, bj = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == EOF)
			return EOF;
		bj = (c == '-' || bj == -1) ? -1 : 1, c = getchar();
	}
	while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar();
	return num * bj;
}
void extgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
	if (!b) { d = a; x = 1; y = 0; }
	else { extgcd(b, a%b, d, y, x); y -= x * (a / b); }
}
int quick_pow(ll a, ll b)
{
	ll ans = 1, t = a;
	while (b)
	{
		if (b & 1) ans = ans * t%mod;
		t = t * t%mod;
		b >>= 1;
	}
	return ans;
}
void init()
{
	T = getint();
}
bool cmp(int a, int b)
{
	return a > b;
}
ll C(int n, int m)
{
	if (n < m) return 0;
	m = min(n - m, m);
	ll up = 1, down = 1;
	for (int i = n; i > n - m; --i) up = (up*i) % mod;
	for (int i = m; i >= 2; --i) down = (down*i) % mod;
	ll d, x, y;
	extgcd(down, mod, d, x, y);
	return up * (x+mod) % mod;
}
void solve()
{
	while (T--)
	{
		ll ans = 0;
		n = getint(); m = getint();
		for (int i = 1; i <= n; ++i)
			a[i] = getint();
		sort(a + 1, a + n + 1, cmp);
		for (int i = 1; i <= n - m + 1; ++i)
		{
			ans = (ans + ((a[i] * C(n - i, m - 1)) % mod)) % mod;
		}
		cout << ans << endl;
	}
}
int main()
{
	init();
	solve();
	//system("pause");
}

Comments