建设道路

NC204872. 建设道路

描述

牛牛国有 $n$ 个城市，编号为 $1-n$ ，第 $i$ 个城市有一个价值 $a_i$ ，牛国的国王牛阔落特别喜欢在牛牛国旅游，并且他不想每次旅游的时候都计算一遍走哪条路最短，于是他决定在任意两个城市之间建立一条双向道路，在第 $i$ 座城市和第 $j$ 座城市之间建立双向道路的代价是 $(a_i-a_j)^2$ ，牛阔落希望你能算出这项工程的花费。由于答案太大，你只需要输出答案模 $1e9+7$ 的余数

输入描述

第一行一个整数 $n$ ，表示城市的数量。

第二行 $n$ 以空格分隔的整数 $a1,a2,...,an$ ，表示第i座城市的价值。

输出描述

输出一行一个数字，表示工程的花费模  的余数

示例1

输入:

3
1 2 3

输出:

说明:

城市1到城市2的道路价值是(2 - 1)^ 2 = 1

城市2到城市3的道路价值是(3 - 2)^ 2 = 1

城市1到城市3的道路价值是(3 - 1)^ 2 = 4

总的花费 = 1 + 1 + 4 = 6

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 238ms, 内存消耗: 600K, 提交时间: 2020-04-19 09:24:20

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	long long num=0,num2=0,h=1e9+7,a;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		num=(num+(a*a)%h*(n-1)-(2*(a*num2)%h)%h)%h;
		num2=(num2+a)%h;
	}
	cout<<num;
 }

Python3(3.5.2) 解法, 执行用时: 449ms, 内存消耗: 47224K, 提交时间: 2020-04-20 08:48:25

n = int(input())
s = input().split()
sum=0
res=0
mod=1000000007
for i in range(len(s)):
    t = int(s[i])
    sum += t
    res += t*t*n
res = res - sum*sum
res = res % mod
print(res)

pypy3(pypy3.6.1) 解法, 执行用时: 631ms, 内存消耗: 78780K, 提交时间: 2020-04-18 20:36:10

n=int(input())
l=list(map(int,input().split()))
s=sum(l)
print(sum(i*i*(n-1)-i*(s-i)for i in l)%1000000007)