题解 | #区间权值#

求解:${\sum }_{l=1}^n{\sum }_{r=l}^n{w}_{r-l+1}\ast {\sum }_{i=l}^r{a}_i\backslash sum\_\{l=1\}\; ^n\; \backslash sum\_\{r=l\}\; ^n\; w\_\{r-l+1\}*\backslash sum\_\{i=l\}\; ^ra\_i$
定义：$s_i={\sum }_{j=1}^i{a}_j,su{m}_i={\sum }_{j=1}^i{s}_{j}s\_i=\backslash sum\_\{j=1\}\; ^i\; a\_j\; ,sum\_i=\backslash sum\_\{j=1\}\; ^i\; s\_j$
$⟹\backslash Longrightarrow$ ${\sum }_{l=1}^n{\sum }_{r=l}^n{w}_{r-l+1}\ast (s_r-s_{l-1})\backslash sum\_\{l=1\}\; ^n\; \backslash sum\_\{r=l\}\; ^n\; w\_\{r-l+1\}*(s\_r-s\_\{l-1\})$
换种角度，原命题转换为以r结尾长度为len的区间的所有和
$⟹\backslash Longrightarrow$ ${\sum }_{len=1}^n{w}_{len}\ast {\sum }_{r=len}^n(s_r-s_{r-len})\backslash sum\_\{len=1\}\; ^n\; w\_\{len\}*\backslash sum\_\{r=len\}\; ^n(s\_r-s\_\{r-len\})$
${\sum }_{r=len}^n(s_r-s_{r-len})={\sum }_{r=len}^n{s}_r-{\sum }_{r=len}^n{s}_{r-len}\backslash sum\_\{r=len\}\; ^n(s\_r-s\_\{r-len\})=\backslash sum\_\{r=len\}\; ^ns\_r-\backslash sum\_\{r=len\}\; ^ns\_\{r-len\}$
$⟹\backslash Longrightarrow$ $su{m}_n-su{m}_{len-1}-su{m}_{len}sum\_n-sum\_\{len-1\}-sum\_\{len\}$
所以：${\sum }_{len=1}^n{w}_{len}\ast {\sum }_{r=len}^n(s_r-s_{r-len})={\sum }_{len=1}^n(su{m}_n-su{m}_{len-1}-su{m}_{len})\backslash sum\_\{len=1\}\; ^n\; w\_\{len\}*\backslash sum\_\{r=len\}\; ^n(s\_r-s\_\{r-len\})=\backslash sum\_\{len=1\}\; ^n(sum\_n-sum\_\{len-1\}-sum\_\{len\})$

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
const ll mod = 1e9 + 7;
void dilingtian()
{
    int n;
    cin >> n;
    vector<long long> a(n + 1), w(n + 1), s(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
        sum[i] = sum[i - 1] + s[i];
    }
    long long ans = 0;
    for (int len = 1; len <= n; len++)
      //sum[n]-sum[len-1]-sum[n-len]范围是1e7，w[len]也是1e7，如果直接相乘会爆掉long long
      //所以采用先取余在相乘的做法
        ans = (ans + (sum[n] - sum[len - 1] - sum[n - len] + mod) % mod * w[len] + mod) % mod;
    cout << ans << endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        dilingtian();
    return 0;
}