NC5158 J-建设道路

Question

$\sum_{i=1}^{n}\sum_{j=1}^{n}(a_i-a_j)^2$

Solution

后缀和优化到 $O(n)$
$\sum_{i=1}^{n}\sum_{j=1}^{n}(a_i-a_j)^2=(n-1)\sum_{i=1}^{n}a_i^2-2\sum_{i=1}^{n-1}a_i(suf_{i+1}))$
求一个后缀和优化一下，按公式做就好了。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 5e5 + 5;

ll n,a[N],b[N],suf[N];

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=n;i>=1;i--){
        suf[i]=(suf[i+1]+a[i])%mod;
        b[i]=(n-1)*a[i]%mod*a[i]%mod;
        ans=(ans+b[i])%mod;
    }
    for(int i=2;i<=n;i++){
        ans=(ans-2*a[i-1]%mod*suf[i]%mod+2*mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}