Educational Codeforces Round 115 (Rated for Div. 2) C.D

C.Delete Two Elements

题目大意：给定一个 n n n个元素的序列，定义 k k k为 ∑ i = 1 n a [ i ] n \frac{\sum^{n}_{i = 1}a[i]}{n} n∑i=1n​a[i]​(元素和/ n n n=平均数)，现在要求你删除 2 2 2个元素，使删除前后的序列的 k k k值不变，求删除的方案数目。

思路：考虑删除后使原序列大小不变的情况：两个元素相加等于二倍平均数。

我们对式子进行移项，可得： n × s u m n = n × ∑ i = 1 n a [ i ] n \times \frac{sum}{n} = n \times \sum^{n}_{i = 1}a[i] n×nsum​=n×∑i=1n​a[i]，不难发现对于要删除的两个元素实际上满足 d e l 1 + d e l 2 2 = s u m n \frac{del_1 + del_2}{2} = \frac{sum}{n} 2del1​+del2​​=nsum​。为了避免产生精度误差，将上式子交叉相乘可得： n × d e l 1 + n × d e l 2 = 2 × s u m n \times del_1 + n \times del_2 = 2 \times sum n×del1​+n×del2​=2×sum。

为了避免重复，我们可以处理一组删除一组，利用组合数学计算每组对答案的贡献。

• 如果 x = = y x == y x==y，则贡献为 x × ( x − 1 ) 2 \frac{x \times (x - 1)}{2} 2x×(x−1)​；
• 如果 x ≠ y x \neq y x​=y，则贡献为 x × y x \times y x×y。

#include 
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N];
map mp;

inline void solve(){
    mp.clear();
    int sum = 0, n = 0, ans = 0; cin >> n;
    for(int i = 1; i > a[i];
        sum += a[i];
        mp[n * a[i]]++;
    }
    for(int i = 1; i > a[i][2];
        cnt1[a[i][1]]++, cnt2[a[i][2]]++;
    }
    long long ans = 1ll * n * (n - 1) * (n - 2) / 6;
    for(int i = 1; i