题解：P15546 「Stoi2037」七里香

题面

我的解法篇幅偏长。

思路

\(70\) 分做法

\(70\) 分需要 \(O(n^2)\) 实现，原式中有 \(4\) 个变量肯定不能直接套，需要推式子。

\[\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}[((j-1)k+a_j')-((i-1)k+a_i')] \]

发现 \(l,r\) 不参与计算，对于一组 \(i,j\)，当且仅当 \(l \in [1,i]\) 且 \(r \in [j,n]\) 时会遍历到，因此 \(i,j\) 会被遍历 \(i \times (n-j+1)\) 次，于是可以将 \(\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}\) 转化为 \(\sum_{1\le i < j\le n}i(n-j+1)\)。

\[\begin{aligned} & \sum_{1 \leq l<r \leq n} \sum_{l \leq i<j \leq r}\left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) \left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \end{aligned} \]

此时只需要枚举 \(i,j\)，可以 \(O(n^2)\) 完成，但是难以看出最大值，继续推。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1) \left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) [(j-i)k+(a_{j}^{\prime}-a_{i}^{\prime})] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) (j-i)k+ i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime}) \end{aligned} \]

此时，式子分为常数部分和变量部分，对于左半边，我们可以单独遍历求出。

对于右半部分，发现对于一堆 \(i,j\)，\(a_j^{\prime}\) 的权重为 \(i(n-j+1)\)，\(a_i^{\prime}\) 的权重为 \(-i(n-j+1)\)。

因此，我们可以在遍历时计算各位置的权重并排序，与排序过后的 \(a\) 数组一一对应相乘，并且加上常数部分，即可得出答案。

计算过程中可能出现范围超过 long long 的情况，可以用 int128 解决。

这个做法理论上是 \(70\) 分，但是交上去似乎有 \(80\) 分。

\(100\) 分做法

依旧继续推式子。

对于常数部分，因为和 \(k\) 没关系，所以先把 \(k\) 提出。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1) [(j-i)k+(a_{j}^{\prime}-a_{i}^{\prime})] \\ = & k \sum_{1 \leq i<j \leq n} i(n-j+1)(j-i) \end{aligned} \]

固定 \(i\) 不变，对 \(j\) 求和。令 \(d=j-i\)，则 \(j=i+d\)，\(d \in [1,n-i]\)，令 \(m=n-i\)。

将其代入算出 \(i\) 的求和项。

\[\begin{aligned} & k \sum_{1 \leq i<j \leq n} i(n-j+1)(j-i) \\ = & k \sum_{j=i+1}^n i(n-j+1)(j-i) \\ = & k \sum_{d=1}^m i[n-(i+d)+1] \times d \\ = & k \sum_{d=1}^m i[(n-i+1)-d] \times d \\ = & k \sum_{d=1}^m i[(n-i+1)d-d^2] \\ = & k (\sum_{d=1}^m i + \sum_{d=1}^m [(n-i+1)d-d^2]) \\ = & k (\sum_{d=1}^m i + \sum_{d=1}^m (n-i+1)d- \sum_{d=1}^m d^2) \\ \end{aligned} \]

其中 \(\sum_{d=1}^m i\) 可以单独算出，右半部分考虑运用等差数列求和公式以及平方和公式。

\[\begin{aligned} & \sum_{d=1}^m d=\frac{m(m+1)}{2} \\ & \sum_{d=1}^m d^2=\frac{m(m+1)(2m+1)}{6} \end{aligned} \]

代入原式。

\[\begin{aligned} & k (\sum_{d=1}^m i + \sum_{d=1}^m [(n-i+1)d-d^2]) \\ = & k (\sum_{d=1}^m i + (n-i+1)\times \frac{m(m+1)}{2}-\frac{m(m+1)(2m+1)}{6}) \end{aligned} \]

至此，常数部分推导完毕，接下来看变量部分。

\[\sum_{1 \leq i<j \leq n} i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime}) \]

从 \(70\) 分的做法来说，我们的目标是求出对于 \(1\le i \le n\) 中 \(i\) 的权重。设 \(i\) 的权重为 \(w_i\)，则我们的目标应该是求出以下式子。(\(i\) 和原式重复，所以这里使用 \(p\))

\[\sum_{p=1}^n w_p \times a_p \]

首先，将原式的 \(a_j^{\prime}\) 和 \(a_i^{\prime}\) 分开。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime}) \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1)a_{j}^{\prime}- \sum_{1\le i < j\le n} i(n-j+1)a_{i}^{\prime} \end{aligned} \]

此时分 \(2\) 种情况。

第 \(1\) 种，\(p=j\)，此时 \(i \in [1,p-1]\)。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1)a_{j}^{\prime} \\ = & \sum_{i=1}^{p-1} i(n-p+1)a_{p}^{\prime} \\ = & (n-p+1) \sum_{i=1}^{p-1} i\ a_{p}^{\prime} \\ = & (n-p+1) \times \frac{p(p-1)}{2} \sum_{i=1}^{p-1} i\ a_{p}^{\prime} \end{aligned} \]

即 \(w_p=(n-p+1)\times \frac{p(p-1)}{2}\).

第二种，\(p=i\)，此时 \(j \in [p+1,n]\)。

\[\begin{aligned} & -\sum_{1\le i < j\le n} i(n-j+1)a_{i}^{\prime} \\ = & -\sum_{j=p+1}^n p(n-j+1)a_{p}^{\prime} \\ = & -p \sum_{j=p+1}^n (n-j+1)a_{p}^{\prime} \\ \end{aligned} \]

令 \(t=j-p\)，则 \(t \in [1,n-p]\)，设 \(m=n-p\)。

\[\begin{aligned} & -p \sum_{j=p+1}^n (n-j+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-j+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-j+p-p+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-p+1-t)a_{p}^{\prime} \\ = & -p [\sum_{t=1}^{m} (n-p+1)-\sum_{t=1}^m t ]\sum_{j=p+1}^n a_{p}^{\prime} \\ = & -p [m(m+1)-\frac{m(m+1)}{2}]\sum_{j=p+1}^n a_{p}^{\prime} \\ = & -p \times \frac{m(m+1)}{2}\sum_{j=p+1}^n a_{p}^{\prime} \\ \end{aligned} \]

因此，\(w_p= -p \times \frac{(n-p)(n-p+1)}{2}\)。

将两种情况相加可得，\(w_p=(n-p+1)\times \frac{p(p-1)}{2}-p \times \frac{(n-p)(n-p+1)}{2}\)

经过化简可得，\(w_p=\frac{p(n−p+1)(2p−n−1)}{2}\)。

然后就和 \(70\) 分的操作一样，将权重排序后与排序过的 \(a\) 一一对应相乘，最后加上常数项，即为答案。

计算过程中可能出现范围超过 long long 的情况，可以用 int128 解决。

代码

70分
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int N=1e6+10,LG=30;
int n,k;
int a[N],w[N];
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n=read();k=read();for(int i=1;i<=n;i++){a[i]=read();}sort(a+1,a+n+1);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int cnt=i*(n-j+1);w[i]-=cnt;w[j]+=cnt;}}sort(w+1,w+n+1);int ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){ans+=i*k*(n-j+1)*(j-i);}}for(int i=1;i<=n;i++){ans+=w[i]*a[i];}write(ans);return 0;
}

100分
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int N=2e6+10;
int n,k;
int a[N],w[N];
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n=read();k=read();for(int i=1;i<=n;i++){a[i]=read();}sort(a+1,a+n+1);for(int i=1;i<=n;i++){int m=n-i+1;w[i]=i*m*(2*i-n-1)/2;}sort(w+1,w+n+1);int ans=0;for(int i=1;i<=n;i++){int m=n-i;int sum=(n-i+1)*m*(m+1)/2-m*(m+1)*(2*m+1)/6;ans+=i*sum;}ans*=k;for(int i=1;i<=n;i++){ans+=w[i]*a[i];}write(ans);return 0;
}