建设道路(前缀和优化)

思路：我觉得这个题目有点意思。。。。用一个简单的数学公式展开可以将O(n^2)降到O(n)实属牛皮。
sum1是ai的前缀和，sum2是ai ^ 2的前缀和
${\displaystyle \sum _{i=1}^n}$i=1∑n​ ${\displaystyle \sum _{j=i+1}^n(ai-aj{)}^2}$j=i+1∑n​(ai−aj)2
=> ${\displaystyle \sum _{i=1}^n}$i=1∑n​ ${\displaystyle \sum _{j=i+1}^n(a{i}^2-2\ast ai\ast aj+a{j}^2)}$j=i+1∑n​(ai2−2∗ai∗aj+aj2)
=> ${\displaystyle \sum _{i=1}^n(n-i)\ast a{i}^2}$i=1∑n​(n−i)∗ai2 + ${\displaystyle \sum _{j=i+1}^{n}a{j}^2}$j=i+1∑n​aj2 - 2ai ${\displaystyle \sum _{j=i+1}^{n}aj}$j=i+1∑n​aj
=> ${\displaystyle \sum _{i=1}^n(n-i)\ast a{i}^2-2\ast ai\ast sum1\left[n\right]-sum\left[i\right]+sum2\left[n\right]-sum2\left[i\right]}$i=1∑n​(n−i)∗ai2−2∗ai∗sum1[n]−sum[i]+sum2[n]−sum2[i]

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10; 
typedef long long int ll;
ll mod = 1e9 + 7;
ll a[maxn];
ll sum1[maxn],sum2[maxn];
void solved(){
	int n;scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%lld",&a[i]);
		sum1[i] = (sum1[i - 1] + a[i]) % mod;
		sum2[i] = (sum2[i - 1] + a[i] * a[i] % mod) %mod; 
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		ans += (((n - i) * a[i] % mod * a[i] % mod) %mod - (2 * a[i] % mod * (sum1[n] - sum1[i] + mod) %mod) %mod + (sum2[n] - sum2[i] + mod)%mod)%mod; 
	}
	printf("%lld\n",ans%mod);
}
int main(){
	solved();
	return 0;
} 

感觉这样的题目还是蛮有意思的。