题目描述
首先记a1+a2+a3+a4+......+an=sum;
用s记录答案;
对于任意n;
s= a1 * ( a2 + a3 + a4 + ...... + a(n-1) + an ) // a1 (s-a1);
+a2 * ( a3 + a4 + ...... + a(n-1) + an )
+a3 * ( a4 + ...... + a(n-1) + an )
......
+a(n-2) * ( a(n-1) + an )
+a(n-1) * ( an )
还会等于
= a2 * ( a1 )
+a3 * ( a1 + a2 )
+a4 * ( a1 + a2 + a3 )
+......
+a(n-1)( a1 + a2 + a3 + ...... + a(n-2) )
+an * ( a1 + a2 + a3 + ...... + a(n-2) + a(n-1 ); // an * (sum-an);
所以
s+s= a1 * (sum-a1) + a2 * (sum-a2)+......+an * (sum-an);
献上代码
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int maxn=2001000;
long long a[maxn],g[maxn];
int n;
long long sum=0,s=0;
/法一:推公式
int main()
{
cin>>n;
for(int i=1;i<=n;i)
{
cin>>a[i];
sum+=a[i];
}
for(int i=1;i<=n;i)
{
s+=a[i](sum-a[i]);
}
s/=2;
cout<<s;
}/
/法二:前缀和
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int maxn=2001000;
long long a[maxn],g[maxn];
int n;
long long sum=0,s=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i)
{
cin>>a[i];
g[i]=g[i-1]+a[i-1];
}
for(int i=2;i<=n;i)
{
s+=a[i]*g[i];
}
cout<<s;
}