题解 P3909 【异或之积】

· · 题解

题意简述：

给定序列 a，求 6×\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}a_ia_ja_k 的值。

题目解法：

这里分享一种时间复杂度 O(n)，空间复杂度 O(1)，算上快读代码长度仅为 549B 的做法。

先推一波式子：

\ \ \ \ 6×\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}a_ia_ja_k =6×\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1}\sum\limits_{k=1}^{j-1}a_ia_ja_k =6×\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}\sum\limits_{k=1}^{j-1}a_ja_k =6×\sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k

然后 for 循环一遍，同时记录 \sum\limits_{k=1}^{j-1}a_k，再用 \sum\limits_{k=1}^{j-1}a_k 来更新 \sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k，最后用 \sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k 来更新答案 \sum\limits_{i=1}^{n}a_i\sum\limits_{j=1}^{i-1}a_j\sum\limits_{k=1}^{j-1}a_k 即可。
值得注意的是这三个变量更新的顺序要注意，而且答案要记得 ×\space6。

最后，记得开 long long !

正确代码：

#include<bits/stdc++.h> 
#define int long long
#define mod 1000000007
using namespace std;
inline int read(){
    int res=0;
    bool zf=0;
    char c;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    return (zf?-res:res);
}
signed main(){
    int n=read(),sum1=0,sum2=0,sum3=0;
    for(register int i=1;i<=n;++i){
        int t=read();
        sum3=(sum3+sum2*t)%mod;
        sum2=(sum2+sum1*t)%mod;
        sum1=(sum1+t)%mod;
    }
    printf("%d\n",sum3*6%mod);
    return 0;
}

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 \text{OIer}。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 \text{OIer}。