7月21日区间权值

题解：
把这个双重求和公式按照最简单的方法展开，可以将其n=3，4，5都展开，观察其式子规律
n=5时，
(a1 + a2 + a3 + a4 + a5) * w1+
(a1 + 2 * a2 + 2 * a3 + 2 * a4 + a5) * w2+
(a1 + 2 * a2 + 3 * a3 + 2 * a4 + a5) * w3+
(a1 + 2 * a2 + 2 * a3 + 2 * a4 + a5) * w4+
(a1 + a2 + a3 + a4 + a5) * w5
下面为n=4的时候展开方法。

展开三四项发现其规律后，就利用前缀和在O(1)的复杂度下计算出区间长度即可

/*Keep on going Never give up*/
#include <bits/stdc++.h>
const int maxn = 3e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
ll a[maxn],ans[maxn],w[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]=(a[i-1]+a[i])%mod;
    }
    ll ans=0,sum=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
    }
    for(int i=1;i<=n/2;i++){
        sum=(sum+a[n-i+1]-a[i-1]+mod)%mod;
        ans=(ans+sum*w[i]+sum*w[n-i+1])%mod;
    }
    if(n%2!=0) ans=(ans+(sum+a[n/2+1]-a[n/2])*w[n/2+1])%mod;
    cout<<ans<<endl;
}