[CF]1445D Divide and Sum

题意:

一个长度为(2n)的序列,任取(n)个加入(A)集合,剩余加入(B)集合。
(A)集合升序排序,(B)集合降序排序,两个集合之间对应元素作差的绝对值之和(sum|x_i-y_i|)记为(f)
每个元素都看成是不同的(相同大小也不同),求可能的取法的(f)之和。

题解:

想了一会儿没啥想法。
然后想到了去绝对值。
去掉绝对值之后,每个元素对于答案的贡献一部分是正一部分是负,接下来就考虑正负的关系就行了。

考虑(n==2)的情况,记四个元素为(a,b,c,d)(从小到大排序)。
手动列出所有(6)种情况,发现(a,b)永远是负的,(c,d)永远是正的,猜测是否前(n)个恒负,后(n)个恒正。

现证明:
(n)个元素用(u)表示,后(n)个元素用(v)表示
假设(A)集合中有(k)(u),于是他有(n-k)(v)
于是在(B)集合中有(n-k)(u)(k)(v)
排序后发现(A)中的(u)都对上(v)(v)都对上(u),又(u)是恒小于等于(v)的,于是证明(u)的贡献一定为负,而(v)的贡献一定为正。

最后再乘上所有的方案数就行了。

#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
const int mod = 998244353;
int read(){
	char c; int num, f = 1;
	while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
	while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
	return f * num;
}
const int N = 1e6 + 1009;
int n, base = 1, a[N], ans, inv[N];
signed main()
{
	n = read();
	inv[1] = 1;
	for(int i = 2; i <= n; i++)
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for(int i = 1; i <= n; i++)
		base = base * inv[i] % mod;
	for(int i = n + 1; i <= 2 * n; i++)
		base = base * i % mod;
	for(int i = 1; i <= 2 * n; i++) a[i] = read();
	sort(a + 1, a + 1 + 2 * n);
	for(int i = 1; i <= n; i++) 
		ans = (ans - a[i]) % mod;
	for(int i = n + 1; i <= n * 2; i++) 
		ans = (ans + a[i]) % mod;
	ans = (ans + mod) % mod;
	ans = ans * base % mod;
	printf("%lld
", ans);
	return 0;
}
原文地址:https://www.cnblogs.com/onglublog/p/14376098.html