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

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

[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 后的结果。

5

11 22 33 44 55

12 34 56 78 90

【数据范围】

对于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。

当然，我可以帮你解释这一段 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. 将所有这些最大值相加。

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