题解：P5686 [CSP-S2019 江西] 和积和

· · 题解

题目链接

首先遇到这种题不要慌，可以先转化为前缀和，A 是 a 的前缀和，A 是 b 的前缀和，于是式子变成：

\sum_{i=l}^r (A_r-A_{l-1})\times \sum_{i=l}^r (B_r-B_{l-1})

拆开，变成：

\sum_{i=l}^{r}(A_r\times B_r-A_r\times B_{l-1}-B_r\times A_{l-1}+A_{l-1}\times B_{l-1})

我们首先枚举一个端点，此处枚举的是 r，当然 l 应该也能做，不过可能会难想一点。

对于每一个 r，对答案的贡献是：

r\times A_r\times B_r-A_r\times\sum_{l=1}^{r}B_{l-1}-B_r\times\sum_{l=1}^{r}A_{l-1}+\sum_{l=1}^{r}A_{l-1}\times B_{l-1}

对于 \sum_{l=1}^{r}B_{l-1}、\sum_{l=1}^{r}A_{l-1} 和 \sum_{l=1}^{r}A_{l-1}\times B_{l-1} 这种直接预处理一下前缀和就可以做到 O(1) 复杂度了。

于是就做完了，时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define N 500005
#define ll long long
#define mod 1000000007
using namespace std;

ll n,ans,a[N],b[N],sa[N],sb[N],qja[N];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        a[i]+=a[i-1];
        a[i]%=mod;
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",b+i);
        b[i]+=b[i-1];
        b[i]%=mod;
    }
    for(int i=1;i<=n;i++){
        sa[i]=(sa[i-1]+a[i])%mod;
        sb[i]=(sb[i-1]+b[i])%mod;
    }
    for(int i=1;i<=n;i++)qja[i]=(qja[i-1]+(a[i]*b[i])%mod)%mod;
    for(int i=1;i<=n;i++){
        ans=(ans+((i*a[i])%mod*b[i])%mod)%mod;
        ans=(ans-((a[i])%mod*sb[i-1])%mod+mod)%mod;
        ans=(ans-((sa[i-1])%mod*b[i])%mod+mod)%mod;
        ans=(ans+qja[i-1])%mod;
    }
    printf("%lld\n",ans);
    return 0;
}