自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 21:53:58，当前版本为作者最后更新于2020-09-26 20:13:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

给定序列 $a$，求 $6×\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}a_ia_ja_k$ 的值。

题目解法：

这里分享一种时间复杂度 $O(n)$，空间复杂度 $O(1)$，算上快读代码长度仅为 $549B$ 的做法。

先推一波式子：
$\ \ \ \ 6×\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}a_ia_ja_k$
$=6×\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1}\sum\limits_{k=1}^{j-1}a_ia_ja_k$
$=6×\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}\sum\limits_{k=1}^{j-1}a_ja_k$
$=6×\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k$
然后 for 循环一遍，同时记录 $\sum\limits_{k=1}^{j-1}a_k$，再用 $\sum\limits_{k=1}^{j-1}a_k$ 来更新 $\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k$，最后用 $\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k$ 来更新答案 $\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k$ 即可。
值得注意的是这三个变量更新的顺序要注意，而且答案要记得 $×\space6$。

最后，记得开 long long !

正确代码：

#include<bits/stdc++.h> 
#define int long long
#define mod 1000000007
using namespace std;
inline int read(){
	int res=0;
	bool zf=0;
	char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-')zf=1;
	else res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
	return (zf?-res:res);
}
signed main(){
	int n=read(),sum1=0,sum2=0,sum3=0;
	for(register int i=1;i<=n;++i){
		int t=read();
		sum3=(sum3+sum2*t)%mod;
		sum2=(sum2+sum1*t)%mod;
		sum1=(sum1+t)%mod;
	}
	printf("%d\n",sum3*6%mod);
	return 0;
}

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 $\text{OIer}$。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 $\text{OIer}$。