CF1165E Solution

OIerWu_829 · 2025-01-13 11:14:14 · 题解

洛谷传送门 / Codeforces 传送门

不难发现 a_i 的贡献为 a_i\times(n-i+1)\times i，所以我们在输入的时候把 a_i 乘上 (n-i+1)\times i，然后把 a 数组从小到大排序，把 b 从大到小排序，这样就可以形成差大积小，然后累加 a_i\times b_i 就可以了。

注意取模的问题，坑了我好久。

#include <iostream>
#include <algorithm>
using namespace std;

using LL = long long;

const LL N = 2e5 + 5;
const LL mod = 998244353;

LL a[N], b[N];

int main()
{
    LL n;
    cin >> n;
    for (LL i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] *= (n - i + 1) * i;
    }
    for (LL i = 1; i <= n; i++)
        cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n, greater<LL>());
    LL ans = 0;
    for (LL i = 1; i <= n; i++)
        ans += a[i] % mod * b[i] % mod;
    cout << ans % mod;
    return 0;
}