D. Divide and Sum (组合数、思维)

痛定思痛。 2021-07-16 18:48 334阅读 0赞

[添加链接描述][Link 1]

对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。

看例子 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 （已按大小排序）

假设对于第一组 取了前面3个，后面2个，然后其从很小到大排序，后面一组只可能是取前面2个，后面3个，从大到小排序。那么对于第一组的前3个（顺序）与后面一组的前3个（逆序），必然是第一组的前三个都是a，后面一组的前三个都是b,然后对于第一组后两个，和后一组后两个，第一组后两个必然是b,后一组后两个必然是a。将绝对值去掉一组的差值就等于b1+b2+b3+b4+b5-a1-a2-a3-a4-a5，所有情况都是如此，将上例3化为k,2化为n-k就是普遍情况。然后总共有从2n个取出n个的情况，相乘即可。

#include<iostream>
    #include<algorithm>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll lst[Max];
    ll Mod = 998244353;
    
    ll f[Max];
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    void init() { 
    	f[0] = 1;
    	for (int i = 1;i <= 1e6;i++) { 
    		f[i] = f[i - 1] * i % Mod;
    	}
    }
    ll cal(ll n, ll m) { 
    	if (n < m) return 0;
    	return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
    }
    
    int main()
    { 
    	ll n;cin >> n;
    	init();
    	for (int i = 1;i <= 2*n;i++)cin >> lst[i];
    	ll ans = 0;
    	sort(lst + 1, lst + 1 + 2*n);
    	for (int i = 1;i <= n;i++)
    	{ 
    		ans += lst[2 * n - i + 1] - lst[i];
    	}
    	ans = (ans % Mod * cal(n * 2, n)) % Mod;
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/contest/1445/problem/D