【[ABC151E] Max-Min Sums】题解

思路

我们不可能暴力枚举所有子集，所以考虑每个元素对答案的贡献。

注意到，在一个子集中，只有头尾两个元素对答案有贡献。当一个元素为子集中最大值时，对答案有一个正的贡献；当为最小值时，有一个负的贡献。
因此，只需要对于每个元素，求出其作为最大和最小值的次数就可以了。

我们先考虑最大值的情况，最小值同理。

显然，对于一个元素，其为子集中最大值，当且仅当其余元素都不大于该元素。
考虑排序，将大小关系转化为先后顺序。则对于一个下标

i

，其作为最大值的子集为前

i-1

个元素中选出

k-1

个再加上它本身，即该元素的正贡献为

{i-1\choose k-1}A_i

。

同理，负贡献为

{n-i\choose k-1}A_i

，总贡献为

[{i-1\choose k-1}-{n-i\choose k-1}]A_i

。

而计算组合数，对于能看到这里的选手来说，一定是 trivial 的。

显然有：

{n\choose m}\equiv n!(m!)^{-1}[(n-m)!]^{-1}\mod 10^9+7

预处理乘法逆元即可。

AC Code

CPP

#include <bits/stdc++.h>
#define UP(i, l, r) for(int i = (l); i <= (r); ++ i)
#define DN(i, l, r) for(int i = (r); i >= (l); -- i)
#define LUP(i, l, r) for(ll i = (l); i <= (r); ++ i)
#define LDN(i, l, r) for(ll i = (r); i >= (l); -- i)
#define FE(i, s) for(auto i : s)
#define PB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 0x3f3f3f3f, INFB = 0x3f, N = 1e5, MOD = 1e9 + 7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, k, a[N + 5];
ll fac[N + 5], ifc[N + 5], ans;

ll qpow(ll a, ll b){
	ll res = 1ll;
	for(; b; b >>= 1){
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

ll md(ll x){ return (x % MOD + MOD) % MOD; }

ll c(ll n, ll m){ return n >= m ? (fac[n] * ifc[m] % MOD) * ifc[n - m] % MOD : 0; }

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	fac[0] = 1;
	UP(i, 1, n){
		cin >> a[i];
		fac[i] = fac[i - 1] * i % MOD;
	}
	ifc[n] = qpow(fac[n], MOD - 2);
	DN(i, 0, n - 1) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
	sort(a + 1, a + n + 1);
	UP(i, 1, n) ans = md(ans + md(md(c(i - 1, k - 1) - c(n - i, k - 1))) * a[i]);
	cout << ans;
}

【[ABC151E] Max-Min Sums】题解

文章操作

思路

AC Code

相关推荐

评论

【[ABC151E] Max-Min Sums】题解