题解 P3909 【异或之积】
ESTELLE_1017
2019-07-01 20:56:38
##前言
这道题我是找规律找的。
##证明如下：
首先我们枚举(a[1]*a[2])开始的式子：
a[1]*a[2]*a[3]+a[1]*a[2]*a[4]+...+a[1]*a[2]*a[n].
然后提取（a[1]*a[2]），可以得到：
(a[1]*a[2])*(a[3]+a[4]+...+a[n]).
于是我们用一个前缀和数组f维护一下，f[i]表示前i个数的和。
```cpp
for(int i=1;i<=n;i++){
f[i]=f[i-1]+a[i];
}
```
所以式子就变成了：
(a[1]*a[2])*(f[n]-f[2])
同样我们可以得到(a[1]*a[3])开始的式子：
(a[1]*a[3])*(f[n]-f[3])
所以以a[1]开始的式子为：
a[1]*(a[2]*(f[n]-f[2])+a[3]*(f[n]-f[3])+...+a[n]*(f[n]-f[n]))
去括号得到：
a[1]*(a[2]*f[n]+ a[3]*f[n]+ ...+ a[n]*f[n]- a[2]*f[2]- a[3]*f[3]- ...- a[n]*f[n])
提取一个f[n]可以得到：
a[1]*(f[n]*(a[2]+a[3]+...+a[n])-a[2]*f[2]-a[3]*f[3]-...-a[n]*f[n])
然后我们再定义一个数组c,c[i]表示前i个（a[i]*f[i])的和。
```cpp
for(int i=1;i<=n;i++){
c[i]=c[i-1]+(a[i]*f[i]);
}
```
所以式子又变为：
a[1]*(f[n]*(f[n]-f[1])-(c[n]-c[1]))
然后我们就可以通过a[1]的例子推导出公式：
ans=ans+(a[i]*(f[i]*(f[n]-f[i])-(c[n]-c[i]));
然后我们就可以O(n)枚举求出结果了。
##补充
记得开long long ，然后%mod之前先加mod，（其实有些题解没有加上mod，但
是我的不加就会WA，可能我比较弱吧）
##下面赋上代码（因为WA了几次所以疯狂%，略丑勿怪）：
```cpp
#include<bits/stdc++.h>
#define N 1000005
const long long p=1e9+7;
using namespace std;
long long n,ans,a[N],f[N],c[N];
inline long long read(){
long long r=0,t=1,c=getchar();
while(c<'0'||c>'9'){
t=c=='-'?-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
r=r*10+c-48;
c=getchar();
}
return r*t;
}//快读
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=(read()+p)%p,f[i]=((f[i-1]+a[i])+p)%p;
for(int i=1;i<=n;i++)
c[i]=((c[i-1]+((f[i]*a[i])+p)%p+p)%p+p)%p;
for(int i=1;i<=n-2;i++){
ans=((ans+(((a[i]+p)%p)*((((((f[n]-f[i])+p)%p)*(f[n]%p))%p)-(((c[n]-c[i])+p)%p+p)%p))%p)+p)%p;
}
ans=((ans*6)+p)%p;
printf("%lld",(ans+p)%p);
return 0;
}
```