洛谷 P5686 [CSP-SJX2019]和积和

luogu P5686

做这个题你需要知道啥：

做这个题你要知道前缀和是什么东西。
你还需要知道sigma的性质:
\(\displaystyle \sum_{i - 1}^{n}t\)(t为常数)， 那么则有\(\displaystyle \sum_{i - 1}^{n}t = n \ast t\)
\(\displaystyle \sum_{i - 1}^{n}t * s_i\)(t为常数), 那么则有\(\displaystyle \sum_{i - 1}^{n}t \ast s_i= t \ast \sum_{i = 1}^{n}s_i\)

我们进入正题（敲黑板）.

\[\sum_{l = 1}^{n} \sum_{r = l}^{n} (\sum_{i = l}^{r}A_i \ast \sum_{i = l}^{r}B_i)\]
直接求得话你就有40分\(O(n ^3)\)的高分了。
记SA为A的前缀和数组， SB为B的前缀和数组
\[则原式=\sum_{l = 1}^{n} \sum_{r = l}^{n} (SA[r] - SA[l - 1]) \ast (SB[r] - SB[l - 1])\]
这样你就有70分的高分了。
把上边的式子化简出来就是:
\[=\sum_{l = 1}^{n} \sum_{r = l}^{n} (SA[r] \ast SB[r] - SA[l - 1] \ast SB[r] \]
\[- SA[r] \ast SB[l - 1] + SA[l - 1] \ast SA[l - 1])\]
然后我们发现\(SA_i \ast SB_i\)似乎可以前缀和求出来，而且中间两个减去的可以前缀和求出\(SA_r 与 SB_r\)的值。
那么我们用qz数组来表示\(SA_i \ast SB_i\)的前缀和，然后用qza来表示SA的前缀和，用qzb来表示SB的前缀和，然后我们就可以求解了。
所以最后式子化简出来就是：
\[\sum_{i = 1}^{n}(qz[n] - qz[i - 1]) - SA[i - 1] \ast (qzb[n] - qzb[i - 1]) \]
\[- SB[i - 1] \ast (qza[n] - qza[i - 1]) + (n - r + 1) \ast SA{i - 1} \ast SB[i - 1]\]
最后的时候注意取膜（取膜不当火葬场）。
注意一下%掉1e9+7之后再相减的时候会出现负数。

#include <cstdio>
#include <iostream>

#define N 500010
#define M 1010
#define ll long long

using namespace std;
const int mod = 1e9 + 7;
int n;
ll a[N], b[N], sa[N], sb[N], qz[N], qza[N], qzb[N];

ll read() {
    ll s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read(), sa[i] = (sa[i - 1] + a[i]) % mod;
    for (int i = 1; i <= n; i++)
        b[i] = read(), sb[i] = (sb[i - 1] + b[i]) % mod;
    for (int i = 1; i <= n; i++) {
        qza[i] = (qza[i - 1] + sa[i]) % mod;
        qzb[i] = (qzb[i - 1] + sb[i]) % mod;
        qz[i] = (sa[i] * sb[i] % mod + qz[i - 1]) % mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll sf = (qz[n] - qz[i - 1] + mod) % mod;
        ll sy = ((qzb[n] - qzb[i - 1] + mod) % mod * sa[i - 1]) % mod;
        ll sq = ((qza[n] - qza[i - 1] + mod) % mod * sb[i - 1]) % mod;
        ll sp = ((n - i + 1) * ((sa[i - 1] * sb[i - 1]) % mod)) % mod;
        ans = (ans + sf - sy - sq + sp + mod) % mod;
    }
    cout << ans;
}

洛谷 P5686 [CSP-SJX2019]和积和

原文：https://www.cnblogs.com/zzz-hhh/p/12042126.html