题解 P3909 【异或之积】
Hexarhy
2020-11-29 20:43:12
### Preface
基础题，练反应~~然而我还是干瞪眼了半天~~。
### Solution
如果熟悉 trick，可以很快推出来。
但是如果是像我这样的萌新，还是要多举例子找规律。
例如 $n=4$，式子展开为：
$$a_1a_2a_3+a_1a_2a_4+a_1a_3a_4+a_2a_3a_4$$
$$=a_1\cdot a_2\cdot (a_3+a_4)+(a_1+a_2)\cdot a_3\cdot a_4$$
好像有规律了。对于一个单项式，把中间的元素作为标准分个类。
再比如 $n=5$ 时：
$$a_1a_2a_3+a_1a_2a_4+a_1a_2a_5+a_1a_3a_4+a_1a_3a_5+a_1a_4a_5+
a_2a_3a_4+a_2a_3a_5+a_2a_4a_5+a_3a_4a_5$$
$$=a_1\cdot a_2\cdot(a_3+a_4+a_5)+(a_1+a_2)\cdot a_3\cdot(a_4+a_5)+(a_1+a_2+a_3)\cdot a_4\cdot a_5$$
记前缀和为 $pre_i$，后缀和为 $suf_i$，那么答案为：
$$\sum_{i=1}^{n-2}pre_i\times a_{i+1}\times suf_{i+2}$$
时间复杂度 $\Theta(n)$。
### Notice
- 可能要开 `unsigned long long`。
- 随手就要取模。
### Code
```cpp
int main()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+a[i])%MOD;
for(int i=n;i>=1;i--) suf[i]=(suf[i+1]+a[i])%MOD;
for(int i=1;i<=n-2;i++) ans=(ans+1ll*pre[i]*a[i+1]%MOD*suf[i+2]%MOD)%MOD;
cout<<ans*6%MOD<<endl;
return 0;
}
```