NC19798 前缀和

https://ac.nowcoder.com/acm/problem/19798

水题。
推推公式发现，最终的答案等于求和（数列a的所有区间和w(区间长度)）。对于每一个区间长度k，共有n-k+1个区间和它对应。并且这些区间的区间和总和呈现出一种累加的、三角形式的关系，例如样例中k=2时区间和总和=a1+2a2+a3。且区间长度k和n-k对应的区间和总和是一样的。这个总和可以用前缀和递推O（1）地求出，所以整体复杂度On。

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

#define ll long long
const int maxn=3e5+4;
const int mod=1e9+7;
ll a[maxn],sum[maxn],w[maxn];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        cin>>w[i];
    ll tmp=0,ans=0;
    for(int i=1;i<=(n+1)/2;i++){
        tmp=(tmp+sum[n-i+1]-sum[i-1])%mod;
        ans=(ans+tmp*(w[i]+(n-i+1==i?0:w[n-i+1]))%mod)%mod;
    }
    cout<<ans<<endl;
}