题解：B4466 [海淀区入门组 2025] 函数的和

· · 题解

题目传送门

题目大意

给定两个长度为 n 的数组 a 和 b，定义函数：

f(l,r) = \sum_{i = l}^{r} \ a_i . b_i

你需要重新排列 b 中的元素，使得所有子区间和的总和：

S = \sum_{1≤l≤r≤n}^{} \ f(l,r)

最小，并将结果对 998244353 取模输出。

思路

核心：重排不等式 + 贡献转化

  1. 转化目标：所有子区间和的总和可拆解为每个位置 i 的贡献 a_i \cdot b_i \cdot i \cdot (n - i + 1) 。

  2. 重新排列：要使总和最小，需让大的 b_i 乘小的权重。将 a_i \cdot b_i \cdot i \cdot (n - i + 1) 升序排序，b_i 降序排序，对应相乘求和。

  3. 取模输出：结果对 998244353 取模。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> b[i];
    }

    vector<ll> w(n);
    for (int i = 0; i < n; ++i)
    {
        int pos = i + 1;
        w[i] = (ll)pos * (n - pos + 1);
    }

    vector<ll> x(n);
    for (int i = 0; i < n; ++i)
    {
        x[i] = a[i] * w[i];
    }

    sort(x.begin(), x.end());
    sort(b.begin(), b.end(), greater<ll>());

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ans = (ans + (x[i] % MOD) * (b[i] % MOD)) % MOD;
    }
    cout << ans << endl;

    return 0;
}

完结撒花。