区间权值_牛客博客

题意： 给定长度为 $n$ 的序列 $a$ 和 $w$ ,求 $\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$ ，其中 $f(l,r)=(\sum_{i=l}^{r}a_i)\times w_{r-l+1}$ ，答案对 $10^9+7$ 取模
数据范围： $1\leq n\leq 3\times10^5,1\leq a_i\leq 10^7, 1\leq w_i\leq 10^7$

题解：
先计算 $\sum_{i=l}^{r}a_i$

首先考虑长度为 $1$ 的 $a[1,1]+a[2,2]+...+a[n,n]=a[1,n]$
继续考虑长度为 $2$ 的 $a[1,2]+a[2,3]+a[3,4]+...a[n-3,n-1]+a[n-2,n]$ ，考虑取第一项的 $a[1,2]$ 的 $1,2$ ，第二项 $a[2,3]$ 的 $3$ ，...以此到最后一项取 $a[n-2,n]$ 的 $n$ 。所以从第二项开始每项的第一个元素都多了出来即多了 $2,3,4,...,n-1,n$ ，即答案为 $a[1,n]+a[2,n-1]$
再考虑长度为 $3$ 的 $a[1,2,3]+a[2,3,4]+a[3,4,5]+...+a[n-3,n-2,n-1]+a[n-2,n-1,n]$ ，第一项取 $a[1,2,3]$ 的 $1,2,3$ ，第二项取 $4$ ，第三项取 $5$ ,...最后一项取 $n$ 得 $a[1,n]$ ；继续取第二项剩余的 $2,3$ ，第三项的 $4$ ，第四项的 $5$ ，...最后一项的 $n-1$ 得 $a[2,n-1]$ ,剩余可以取第三项的 $3$ ，第四项的 $4$ ，...倒数第二项的 $n-3$ ，最后一项的 $n-2$ 得： $a[3,n-2]$ 。
所以得出结论为 $w_i$ 负责 $\sum_{i=l}^{r}a_i$ 为 $a[1,n]+a[2,n-1]+...+a[i,n-(i-1)],i\in[1,\lfloor\frac{n+1}{2}\rfloor]$
对于 $i>\lfloor\frac{n+1}{2}\rfloor$ ：
继续考虑长度为 $n$ 时，只有一个 $a[1,n]$
再考虑长度为 $n-1$ 时，只有 $a[1,n-1]+a[2,n]=a[1,n]+a[2,n-1]$
再考虑长度为 $n-2$ 时，只有 $a[1,n-2]+a[2,n-1]+a[3,n]=a[1,n]+a[2,n-1]+a[3,n-2]$
可以发现长度为 $1$ 和长度为 $n$ 的 $\sum_{i=l}^{r}a_i$ 一样，长度为 $2$ 和长度为 $n-1$ 一样，长度为 $3$ 和长度为 $n-2$ 一样。
长度为 $i$ 和长度为 $n-(i-1)$ 一样。

注意： 当 $n$ 为奇数时，没有和 $\lfloor\frac{n+1}{2}\rfloor$ 的 $\sum_{i=l}^{r}a_i$ 一样的长度。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
ll all[N], w[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &all[i]), all[i] += all[i - 1];
    for(int i = 1; i <= n; i++) scanf("%lld", &w[i]);

    ll temp = 0, res = 0;
    for(int i = 1; i * 2 <= n + 1; i++) {
        (temp += all[n - (i - 1)] - all[i - 1]) %= mod;
        (res += (w[i] + ((i * 2 == n + 1) ? 0 : w[n - (i - 1)])) * temp) %= mod;
    } 
    printf("%lld\n", res);

    return 0;
}