【每日一题】【7月21日】区间权值

题意：

给定两个长度为 $n$ 的数组 $a$ 和 $w$ ，求 $\sum \limits_{l=1}^n \sum \limits_{r=l}^n (\sum \limits_{i=l}^ra_i) \times w_{r-l+1}$ 。结果对 $10^9 + 7$ 取模。

题解：

喜闻乐见的简单推式子题。

先令 $s_n = \sum \limits_{i=1}^n a_i$ ，即 $s$ 为 $a$ 的前缀和； $t_n = \sum \limits_{i=1}^n w_i$ ，即 $t$ 为 $w$ 的前缀和。

那么：

$\sum \limits_{l=1}^n \sum \limits_{r=l}^n (\sum \limits_{i=l}^ra_i) \times w_{r-l+1} = \sum \limits_{l=1}^n \sum \limits_{r=l}^n (s_r - s_{l-1}) \times w_{r-l+1} = \sum \limits_{l=1}^n \sum \limits_{r=l}^n s_r w_{r-l+1} - \sum \limits_{l=1}^n \sum \limits_{r=l}^n s_{l-1}w_{r-l+1}$

分开算一下

左边：

第一步和式变换，我是从具体表示意义直接写出右边的式子的。两个和式表示的 $[1, n]$ 的所有子区间，原来是先枚举 $l$ ，再枚举 $r$ 。变换一下之后就是先枚举 $r$ ，再枚举 $l$ 。

更详细的和式变换知识可以参考《具体数学》？

$\sum \limits_{l=1}^n \sum \limits_{r=l}^n s_r w_{r-l+1} = \sum \limits_{r=1}^n \sum \limits_{l=1}^r s_r w_{r-l+1} = \sum \limits_{r=1}^n s_r \sum \limits_{l=1}^r w_{r-l+1} = \sum \limits_{r=1}^n s_r \sum \limits_{k=1}^r w_k = \sum \limits_{r=1}^n s_r t_r$

这个式子就可以 $O(n)$ 计算了。

右边不需要和式变换，后面类似地推导。

这里直接给出推导结果：

$\sum \limits_{l=1}^n \sum \limits_{r=l}^n s_{l-1}w_{r-l+1} = \sum \limits_{l=1}^n s_{l-1} t_{n - l + 1}$

式子推完了，这道题就 ok 了。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int a[N], w[N], n;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = (a[i - 1] + a[i]) % mod;
    }
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i] = (w[i - 1] + w[i]) % mod;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = (ans + 1ll * a[i] * w[i] - 1ll * a[i - 1] * w[n - i + 1]) % mod;
    ans = (ans + mod) % mod;
    cout << ans << endl;
    return 0;
}