ABC151 E - Max-Min Sums
April 17, 2020
問題
考えたこと
全部の状態を列挙して、全てのf(X)を求めるのはもちろん間に合わなない
全てのA[i]がmax X or min Xとなる数が何回あるか調べれば
解は(例えばA[i]が全ての選び方のうちmax Xとして4回, min Xとして2回採用されるとしたら) (A[i] * 4) - (A[i] * 2)
これを全てのA[i]について求めれば良さそうだ
A[i]が何回min, maxで選ばれるか？
Xの選び方にはAの元のならびに関する制約がないので、まずAをsortする
これで先頭からみていき, 今見ているA[i]を最小値 or 最大値になるように固定する
A[i]が最大値になる組み合わせは、A[j] 0 < j < iからK-1個を選ぶ組み合わせA[i]が最小値になる組み合わせは、A[j] i < j < nからK-1個を選ぶ組み合わせ
これらは両方とも二項係数(nCk)で求めれる
毎回これを求めてると間に合わないので、考えられる全ての二項係数の組み合わせを、あらかじめ前処理で用意しておけば、O(1)で求めれるので、間に合う
二項係数の前処理とmod逆元
実装で詰まるのはこの2つ
- 二項係数の前処理
- mod逆元
これらは両方ともけんちょんさんの記事がわかりやすいので、それを参照すると良いです
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<int, int> P;
ll modnum = 1e9+7;
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
const int MAX = 1e5+5;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % modnum;
inv[i] = modnum - inv[modnum%i] * (modnum / i) % modnum;
finv[i] = finv[i - 1] * inv[i] % modnum;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % modnum) % modnum;
}
int main() {
ll n, k; cin >> n >> k;
vector<ll> a(n);
rep(i, n) cin >> a[i];
// 二項係数テーブルを作成しておく
COMinit();
sort(a.begin(), a.end());
ll ans = 0;
rep(i, n) {
if(i >= k-1) {
ans += COM(i, k-1) * a[i];
ans %= modnum;
}
if(n-i-1 >= k-1) {
ans -= COM(n-i-1, k-1) * a[i];
ans %= modnum;
}
}
cout << ans << endl;
return 0;
}