建设道路（小白版）

题目链接

https://ac.nowcoder.com/acm/contest/5158/J

题目分析

意思很简单，给出每个城市的价值，求任意俩城市价值差值的平方和。
看到数据你就应该明白，不能暴力啊，这样比较简单的要求自然会想到公式变形。
暴力时间复杂度:O(n*(n-1)/2)

解题思路

先枚举写一下：（单纯的去括号）

把所有的ai^2合并一下：

图片说明

把所有的-2aiaj合并一下：

图片说明

得到最终变形结果：

图片说明

过程实现

第一部分求和比较简单；
第二部分减法部分的求和，通过前缀和实现。遍历ai，ai*后面区间的总和就行了，而后面区间总和用前缀和做差求得。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+20;
const ll mod=1e9+7;
inline ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
ll sum[N]={0};
ll ans=0;
ll a[N];//必开longlong
ll n;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        ans+=(n-1)*(a[i]*a[i]%mod)%mod;
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        ans-=2*a[i]*((sum[n]-sum[i])%mod)%mod;
    }
    cout<<(ans+n*mod)%mod;
}

注意

这里我想强调几点，其实本身想到变形公式并不难，还是难在过程实现和小细节上。
1.我附上一段代码，大家看一下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mod=1e9+7;
ll MOD=1e9+7;
int main(){
    int a=1e7;
    cout<<a*a%mod<<endl;//a为int，mod也为int
    cout<<a*a%MOD<<endl;//a为int，MOD为longlong
    ll b=a;//int转换为longlong
    if(a==b){//判断a和b是不是一个值，int转换为longlong数值并没变
        cout<<b*b%mod<<endl;//b为longlong，mod为int
        cout<<b*b%MOD<<endl;//b为longlong，MOD也为longlong
    }    
}

再附上输出结果

我想表达什么呢？
一开始，我就陷入这个坑里了，一直de不出来。
在举例的代码段中，前两个输出是错误的，后两个是正确的。原因在于，前两个输出中a为int类型，两个int类型相乘的结果在计算机底层是放在了一个存储int类型的寄存器中，从而发生了截断，导致再取模依旧是错误的。后两个输出中b为longlong型，就避免了这种情况的发生，虽然之后对int类型取模，但是会按longlong处理，所以没有影响。
2.因为是减法与取模，所以最后记得加上mod再取模，因为直接得到的ans可能为负数。
3.尽量多得使用取模运算，两个数相乘之后就要取模一次，这样比较保险。