Python：每日一题之求和（前缀和）

问题描述

给定 n 个整数 a1​,a2​,⋅⋅⋅,an​ 求它们两两相乘再相加的和即

S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a1​,a2​,⋯,an​。

输出格式

输出一个整数 S表示所求的和。请使用合适的数据类型进行运算。

样例输入

4
1 3 6 9

样例输出

117

评测用例规模与约定

对于 30% 的数据1≤n≤1000,1≤ai​≤100 。

对于所有评测用例 1≤n≤200000,1≤ai​≤1000 。

参考代码

n=int(input())
a=[0]+[int(i) for i in input().split()]  #读入a[1]~a[n]
s=0
sum=[0]*(n+1)
for i in range(1,n):
  sum[i]=a[i]+sum[i-1]    #计算前缀和sum[1]~sum[n-1]
for i in range(1,n):
  s+=sum[i]*a[i+1]        #计算和
print(s)

思考

本题利用前缀和能得到100%的分数,用暴力方法的话只能得到30%的分数

把计算式子变换为
S=(a1+a2+...+an-1)*an+(a1+a2+..+an-2)*an-1+(a1+a2+...+an-3)*an-2+...+(a1+a2)*a3+a1*a2

其中括号内的部分是前缀和 sum[i]=a1+a2+..+ai
把上式改为S=sum[n-1]*an,+ sum[n-2]*an-1+ sum[n-3]*an-2+...+sum[2]*a3 +sum[1]*a[2] 
式子中用到的n-1个前缀和sum[1]~ sum[n-1]只需要做一次for循环就能全部提前计算出来称为预处理或预计算。
【计算步骤】
sum[1]= a[1]
sum[2]=a[1]+ sum[1]

........
sum[n]= a[n] + sum[n-1]