本人看了其它解法,发现本人的解法还是 首创 !
而且我的解法好像和 ( imes 6) 没什么关系 ……
(如果没 ( imes 6),我没还不用算逆元)
别人的思路呢,大都是从 ( imes 6) 想到三个数的全排列,然后交换顺序枚举。
下面看我的方法。
先抛开 ( imes 6).
[sum_{i=1}^n sum_{j=i+1}^n sum_{k=j+1}^n a_i imes a_j imes a_k
]
[= sum_{j=1}^n a_j imes (sum_{i=1}^{j-1} a_i imes sum_{k=j+1}^n a_k)
]
你可能不太明白?但是,今天的推式子很短,你必须步步理解。
实际上,这步是考虑中间数被计算的次数。对它前面的所有数之和和后面数之和,它都会被计算。
根据 乘法原理 ,就可以得到。
我们想到了前缀和:
[s_i = sum_{j=1}^i a_j
]
那么,显然:
[= sum_{j=1}^n a_j imes s_{j-1} imes (s_n - s_j)
]
直接枚举解决问题。
时间复杂度: (O(n)).
实际得分:(100pts).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-')f=-f; ch=getchar();}
ll x=0;while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
const ll N=1e6+1;
const int MOD=1e9+7;
int n; ll a[N];
ll f[N],s[N];
//f[i]=a[i]*(s[n]-s[i])
inline ll solve(ll x) {
return (x<0)?(x+MOD):x;
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read(),s[i]=(s[i-1]+a[i])%MOD;
for(int i=1;i<=n;i++) f[i]=((a[i]*solve(s[n]-s[i])%MOD)*(s[i-1]))%MOD;
ll ans=0;
for(int i=1;i<=n;i++) ans=(ans+f[i])%MOD;
// for(int i=1;i<=n;i++) printf("%d %lld
",i,f[i]);
printf("%lld
",(ans*6)%MOD);
return 0;
}