P5686

· · 题解

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

有异于其他题解的做法，我采用的是分治的方式来解决这道题目。

思路

所谓分治，就是对于所求区间 [l,r]，取其中点 mid=\frac{l+r}2，分割成两个子区间 [l,mid] 和 (mid,r]，分别计算两个子区间对答案的贡献，再计算所有 l_0\in[l,mid]，r_0\in(mid,r]，[l_0,r_0] 对答案的贡献。

不过，我们需要在 l=r 时停止递归。

在本题中，在 l=r 时，区间 [i,i] 对于答案的贡献就是 a_ib_i；

对于区间 [l,r]，记函数 s_a(l,r)=\sum^{r}_{i=l}a_i，s_b(l,r)=\sum^{r}_{i=l}b_i，区间 [l,r] 的和积，记为函数 f(l,r)，形象地：f(l,r)=s_a(l,r)\times s_b(l,r)。

根据初中数学乘法公式，(a+b)(c+d)=ac+ad+bc+bd。

考虑对于两个区间：[l_0,mid] 和 (mid,r_0]（l\leq l_0\leq mid，mid<r_0\leq r），它们合并产生的和积，显然 f(l_0,r_0)=s_a(l_0,mid)\times s_b(l_0,mid)+s_a(l_0,mid)\times s_b(mid+1,r_0)+s_a(mid+1,r_0)\times s_b(l_0,mid)+s_a(mid+1,r_0)\times s_b(mid+1,r_0)，如果我们可以求出和积，那么求和积和也就简单了。

考虑维护预处理 l_0，显然应该从 mid 到 l 倒序枚举。求前缀和维护 s_a(i,mid) 和 s_b(i,mid)，由于每个 r_0 都可以和 l_0\in[l,mid] 中的任意一个 l_0 维护，所以我们要将 s_a(i,mid) 和 s_b(i,mid) 再次累加起来，同时，由于我们求的是和积的和，所以，每个 [l_0,mid] 也可以独自对答案产生贡献，所有的 [l_0,mid] 都会被包含在 [l_0,r'] 的和积中，而 r'\in[mid+1,r]，共 r-mid 种取值，所以对答案的贡献就是 s_a(l_0,mid)\times s_b(l_0,mid)\times(r-mid)。

再考虑的就是枚举 r_0，同样处理出前缀和，在对前缀和求和，并且对于每个 r_0 进行计算答案，首先，每个 r_0 都可以自己对答案产生贡献，产生方式和 l_0 相同，即 s_a(mid+1,r_0)\times s_b(mid+1,r_0)\times(mid-l+1)。

最终，两侧 a 和 b 前缀和的和记为 suml_a，sumr_a，suml_b，sumr_b，对答案产生的贡献就是 suml_a\times sumr_b+sumr_a\times suml_b。

采用分治，时间复杂度 O(n\log n)，代码简单，推式子少，思维难度较小，但是时间稍微慢一些。

提示：要开 long long，别忘了处处取模。

代码

// author: syl
// language: c++
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5, mod = 1e9+7;
int a[N],b[N],c[N];
int res=0;
void solve(int l,int r) {
    if(l==r) { res=(res+c[l])%mod; return; }
    int mid=l+r>>1,zca=0,zcb=0,sumal=0,sumbl=0;
    for(int i=mid;i>=l;--i) {
        zca=(zca+a[i])%mod;
        sumal=(sumal+zca)%mod;
        zcb=(zcb+b[i])%mod;
        sumbl=(sumbl+zcb)%mod;
        int lk=zca*zcb;
        res=(res+((zca*zcb)%mod)*(r-mid))%mod;
    } zca=0,zcb=0;
    int sumar=0,sumbr=0;
    for(int i=mid+1;i<=r;++i) {
        zca=(zca+a[i])%mod;
        sumar=(sumar+zca)%mod;
        zcb=(zcb+b[i])%mod;
        sumbr=(sumbr+zcb)%mod;
        res=(res+((zca*zcb)%mod)*(mid-l+1))%mod;
    } res=(res+sumal*sumbr+sumar*sumbl)%mod;
    solve(l,mid),solve(mid+1,r);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),
    cout.tie(nullptr);
    int n; cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    for(int i=1;i<=n;++i) c[i]=(a[i]*b[i])%mod;
    solve(1,n);
    cout<<res%mod<<'\n';
    return 0;
}

我的 AC 记录。