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

题意：

给定两个长度为 的数组 和 ，求 。结果对 取模。

题解：

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

先令 ，即 为 的前缀和；，即 为 的前缀和。

那么：

分开算一下

左边：

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

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

这个式子就可以 计算了。

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

这里直接给出推导结果：

式子推完了，这道题就 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;
}