ABC151 E Max-Min Sums

ABC151 E Max-Min Sums

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc151/tasks/abc151_e

考察

• 式変形すると，となるので各が最大値，最小値となる集合の個数を求めればよいことが分かる
• 考察は比較的素早くできたのにあまりの部分で5WA，，，，，悲しい

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long int ll;
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;


/******************************************************************************************/


struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1]%MOD * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] %MOD * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		if (q < 0 || p < q) return (0LL);
		return (fact[p]%MOD * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};



int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	ll n, k;
	cin >> n >> k;


	Combination comb(n + 10);

	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	ll ans = 0;

	ll maxi = 0;

	ll mini = 0;

	for (int i = 0; i < n; i++)
	{
		mini += (a[i] % MOD) * (comb.C(n - i - 1, k - 1) % MOD);
		mini = (mini + MOD) % MOD;
	}

	reverse(a.begin(), a.end());
	for (int i = 0; i < n; i++)
	{
		maxi += (a[i] % MOD) * (comb.C(n - i - 1, k - 1) % MOD);
		maxi = (maxi + MOD) % MOD;
	}

	cout << (maxi - mini + MOD) % MOD << endl;

	return 0;
}