题解 P5686 【和积和】

· · 题解

题意

已知函数 S(l,r) = \sum\limits_{i=l}^ra_i * \sum\limits_{i=l}^rb_i

求 \sum\limits_{l=1}^n\sum\limits_{r=l}^nS(l,r)

Part 1 20pts

送分部分，留给只会模拟的人

Part 2 70pts

很显然 a_i 和 b_i 可以前缀和处理，设 a 数组前缀和为 prea_i， b 数组前缀和为 preb_i，则对于要求的 S(l,r)，就可以 O(1) 计算得出 S(l,r)

处理完之后就可以暴力两重循环计算并累加 $\sum\limits_{l=1}^n\sum\limits_{r=l}^nS(l,r)

核心部分 code：

for(int i=1;i<=n;++i) prea[i] = prea[i-1] + a[i];
for(int i=1;i<=n;++i) preb[i] = preb[i-1] + b[i];
for(int l=1;l<=n;++l)
for(int r=l;r<=n;++r)
{
    ans += (prea[r] - prea[l-1]) * (preb[r] - preb[l-1]) ;
}

考场上只想到这种做法，5min 打完跑路，时间复杂度 O(n^2)。

Part 3 100pts

对其进行拆分后可以推出公式。

以 n=3 时为例

S(1,1)$ $=$ $prea_1$ $*$ $preb_1 S(1,2)$ $=$ $prea_2$ $*$ $preb_2 S(1,3)$ $=$ $prea_3$ $*$ $preb_3 S(2,2) =$ $prea_2$ $*$ $preb_2$ $-$ $prea_2$ $*$ $preb_1$ $-$ $prea_1$ $*$ $preb_2$ $+$ $prea_1$ $*$ $preb_1 S(2,3) =$ $prea_3$ $*$ $preb_3$ $-$ $prea_3$ $*$ $preb_1$ $-$ $prea_1$ $*$ $preb_3$ $+$ $prea_1$ $*$ $preb_1 S(3,3) =$ $prea_3$ $*$ $preb_3$ $-$ $prea_2$ $*$ $preb_3$ $-$ $prea_3$ $*$ $preb_2$ $+$ $prea_2$ $*$ $preb_2

相加后，在等式右边先加上一个 \sum\limits_{i=1}^3prea_i * preb_i，再减去一个 \sum\limits_{i=1}^3prea_i * preb_i

将符号为正的部分和符号为负的部分分别计算

正的部分：4 * \sum\limits_{i=1}^3{prea_i*preb_i}

负的部分可以通过因式分解得到：(prea_1 + prea_2 + prea_3) * (preb_1 + preb_2 + preb_3)

推而广之，对于任意一个 n 都有：

\sum\limits_{l=1}^n\sum\limits_{r=l}^nS(l,r) =$ $(n+1)$ $*$ $\sum\limits_{i=1}^nprea_i$ $*$ $preb_i$ $-$ $\sum\limits_{i=1}^nprea_i$ $*$ $\sum\limits_{i=1}^npreb_i

时间复杂度 O(n)。

code：

#include"bits/stdc++.h"
using namespace std;
int n；
long long a[500010],b[500010];
long long prea[500010],preb[500010];
long long suma,sumb;
long long ans;
#define mod 1000000007
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        prea[i]=(prea[i-1]+a[i])%mod;
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&b[i]);
        preb[i]=(preb[i-1]+b[i])%mod;
    }
    for(int i=1;i<=n;i++)
    {
        (ans+=(((n+1)*prea[i])%mod)*preb[i])%=mod;
        suma=(suma+prea[i])%mod;
        sumb=(sumb+preb[i])%mod;
    }
    long long tot=(suma[n]*sumb[n])%mod;
    ans=(ans-tot+mod)%mod;
    printf("%lld",ans);
    return 0；
}
//by fairicle