【洛谷P3909】异或之积

题目大意：给定一个 N 个数字组成的序列，求

[left(6 imes sum_{i=1}^{N} sum_{j=i+1}^{N} sum_{k=j+1}^{N} A_{i} imes A_{j} imes A_{k} ight) mod left(10^{9}+7 ight) ]

题解：
各个变量之间相互独立是优化的前提。

[egin{array}{l}{sum_{i=1}^{n} sum_{j=i+1}^{n} sum_{k=j+1}^{n} a_{i} a_{j} a_{k}} \ {=sum_{i=1}^{n} a_{i} sum_{j=i+1}^{n} a_{j} sum_{k=j+1}^{n} a_{k}} \ {=sum_{i=1}^{n} a_{i} sum_{j=i+1}^{n} a_{j} C_{j+1}} \ {=sum_{i=1}^{n} a_{i} B_{i+1}} \ {=sum_{i=1}^{n} a_{i} B_{i+1}} \ {=A_{1}}end{array} ]

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
typedef long long LL;

LL n,a[maxn],sum1[maxn],sum2[maxn],sum3[maxn];

void read_and_parse(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)sum1[i]=(sum1[i-1]+a[i])%mod;
	for(int i=1;i<=n;i++)sum2[i]=(sum2[i-1]+(sum1[n]-sum1[i]+mod)%mod*a[i]%mod)%mod;
	for(int i=1;i<=n;i++)sum3[i]=((sum2[n]-sum2[i]+mod)%mod*a[i]%mod+sum3[i-1])%mod;
}

void solve(){
	LL ans=6*sum3[n]%mod;
	printf("%lld
",ans);
}

int main(){
	read_and_parse();
	solve();
	return 0;
}