求:
\[(6\times \sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^na_ia_ja_k) \bmod (10^9+7)
\]
原式 \(=\)
\[=\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j\sum_{k=j+1}^na_k \=\sum_{i=1}^na_i\sum_{j=i+1}^na_j\sum_{k=j+1}^na_k \\]
记 \(s_i=\sum_\limits{j=i+1}^n a_j\) 。
\[=\sum_{i=1}^na_i\sum_{j=i+1}^na_js_{j+1}\=\sum_{i=n-1}^1a_i\sum_{j=i+1}^na_js_{j}
\]
从后往前扫一遍即可。
代码如下:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
char buf[1 << 25] ,*p1 = buf ,*p2 = buf;
#define getchar() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf ,1 ,1 << 21 ,stdin)) ,p1 == p2) ? EOF : *p1++)
typedef long long LL;
using namespace std;
inline int read() {
int num = 0 ,f = 1; char c = getchar();
while (!isdigit(c)) f = c == ‘-‘ ? -1 : f ,c = getchar();
while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
return num * f;
}
const int mod = 1e9 + 7;
int ans ,n;
signed main() {
n = read();
for (int i = n ,s = 0 ,g = 0; i >= 1; i--) {
int x = read();
ans = (ans + (LL)x * g % mod) % mod;
g = (g + (LL)x * s % mod) % mod;
s = (s + x) % mod;
}
printf("%d\n" ,ans * 6ll % mod);
return 0;
}