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

· · 题解

注意到：

\begin{split} \sum_{l=1}^{n}\sum_{r=l}^{n}\sum_{i=l}^{r}\sum_{j=l}^{r}a_ib_j &= \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{l=1}^{\min\{i, j\}}\sum_{r=\max\{i, j\}}^{n}a_ib_j \\&= \sum_{i=1}^{n}\sum_{j=1}^{n}\min\{i, j\}(n - \max\{i, j\} + 1)a_ib_j \\&= \sum_{i=1}^{n}(n - i + 1)a_i\sum_{j=1}^{i}jb_j + \sum_{i=1}^{n}ia_i\sum_{j=i + 1}^{n}(n - j + 1)b_j \\&= \sum_{i=1}^{n}(n - i + 1)a_i\sum_{j=1}^{i}jb_j + \sum_{j=1}^{n}(n - j + 1)b_j\sum_{i=1}^{j - 1}ia_i \end{split}

迭代计算即可（下面的代码假设数组下标从 0 至 n - 1）：

int s = 0, t = 0;
for(int i = 0; i < n; ++i) {
  t = (t + ll(i + 1) * B[i]) % MOD;
  s = (s + ll(n - i) * A[i] % MOD * t) % MOD;
}
t = 0;
for(int i = 0; i < n; ++i) {
  s = (s + ll(n - i) * B[i] % MOD * t) % MOD;
  t = (t + ll(i + 1) * A[i]) % MOD;
}