准高一考完中考又来打竞赛了，服了，好消息是可以去北大附中本部训练

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

P5686 [CSP-S2019 江西] 和积和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[CSP-S2019 江西] 和积和

题目描述

给定两个下标从$1$到$n$编号的序列$a_i,b_i$，定义函数$S(l,r)(1\le l\le r\le n)$为：

$$\sum_{i=l}^r a_i\times \sum_{i=l}^r b_i$$

请你求出下列式子的值：

$$\sum_{l=1}^n \sum_{r=l}^n S(l,r)$$

由于答案可能很大，你只需要给出答案模$10^9+7$后的结果。

输入格式

第一行一个正整数$n$表示序列长度。

第二行$n$个正整数表示$a_i$。

第三行$n$个正整数表示$b_i$。

输出格式

仅一行一个整数表示答案模$10^9+7$后的结果。

样例 #1

样例输入 #1

3

2 3 4

3 4 5

样例输出 #1

244

样例 #2

样例输入 #2

5

11 22 33 44 55

12 34 56 78 90

样例输出 #2

201542

提示

【数据范围】

对于$20\%$的数据：$n\le 10$,$a_i,b_i\le 10$；

对于$40\%$的数据：$n\le 200$,$a_i,b_i\le 100$；

对于$70\%$的数据：$n\le 3000$,$a_i,b_i\le 10^5$；

对于$100\%$的数据：$3\le n\le 5\times 10^5$,$1\le a_i,b_i\le 10^9$。

初三生看到这个慌了，但是别慌，看ai的解释

当然，我可以帮你解释这一段 LaTeX 代码：

$sum_{l=1}^n\sum_{r=l}^n \max(a[l...r])$

这是一个嵌套求和表达式，分为以下几部分：

1.外层求和$\sum_{l=1}^n$：表示对$l$从 1 到$n$进行求和。

2.内层求和$\sum_{r=l}^n$：在每个固定的$l$值下，表示对$r$从$l$到$n$进行求和。

3.最大值函数$\max(a[l...r])$：表示在数组$a$的子数组$a[l]$到$a[r]$之间取最大值。

组合在一起，这个表达式的意思是：

对于数组$a$中的所有可能的子数组$a[l...r]$（其中$1 \leq l \leq r \leq n$），求这些子数组的最大值的和。

逐步解释如下：

1. 选定左端点$l$从 1 到$n$。

2. 对于每个$l$，选定右端点$r$从$l$到$n$。

3. 计算子数组$a[l]$到$a[r]$的最大值。

4. 将所有这些最大值相加。

总的来说，这个表达式代表的是将所有可能的子数组的最大值进行累加的结果。