4.20 每日一题题解

建设道路

题目链接：https://ac.nowcoder.com/acm/contest/5158/J

涉及知识点：

暴力/取模

solution：

(新的一周，要努力刷题呀！)
(题目可以化简成：)
(sum_{i=1}^n sum_{j=i+1}^n (a^2_i - a^2_j))
(由于数字过大，需要取模)
(n = 1e5，暴力会超时，所以将式子拆分)
(我们可以将式子拆分成两部分：)
(第一部分：(n-1)*(a^2_1 + a^2_2 + ...... + a^2_n))
(第二部分：(-2)*(a_1*a_2 + (a_1 + a_2)*a_3 + (a_1 + a_2 + a_3)*a_4 + ..... ))
(如果看不懂的建议拆一下)
(sum_{i=1}^4 sum_{j=i+1}^4 (a^2_i - aj^2))
(拆分成这两部分之后我们就可以在O(n)的时间内计算出来)
(第二部分的负数怎么取模？)
$ (a - b) mod (c) = (a - b + c) mod (c)$
(当然，python和java更暴力，大数不需要取模，直接计算)

c++ std:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500010;
const int mod = 1e9+7;
long long a[N];
 
int main(){
    int n;
    scanf("%d",&n);
    long long res = 0;
    for (int i = 0; i < n; i ++){
        scanf("%lld",&a[i]);
        res += a[i];
    }
 
    long long ans = 0;

    long long sum = 0;
     
    for (int i = 0; i < n; i++){
        sum += a[i];
        long long x = (n - 1) * a[i] % mod * a[i] % mod;
        long long y = 2 * a[i] %mod *((res - sum) % mod) % mod;
        long long z = (x - y + ans + mod)% mod;
        ans = z;
    }
 
    printf("%lld
",ans);
}

python std:

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)