区间权值

题意 : 给出2个序列，一个是a序列，一个是w序列。 定义：f(l,r)=区间[l,r] ai*Wr−l+1
让你求的是L:[1-r] R:[L-r] 所有f(l,r)求和

分析: 一开始由于没看n的大小，暴力维护所有区间的值，前缀和来统计。但是n=3e5的话，复杂度就是 (n+1)*n/2
妥妥T了。

通过手写前几项，可以发现一定规律
当n=3 ans= (a1+a2+a3)w1+(a1+2a2+a3)w2+(a1+a2+a3)w3
当n=4 ans= (a1+a2+a3+a4)w1+(a1+2a2+2a3+a4)w2+(a1+2a2+2a3+a4)w3+(a1+a2+a3+a4)w4
当n=5 ans= (a1+a2+a3+a4+a5)w1+(a1+2a2+2a3+2a4+a5)w2+(a1+2a2+3a3+2a4+a5)w3+(a1+2a2+2a3+2a4+a5)w4+(a1+a2+a3+a4+a5)*w5

所以很显然是一个前缀和维护，O(n)可以解决,不要忘记取mod

AC代码:

​#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define PI 3.14159265358979323846

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const int N=3e5+100;

ll n;

ll a[N];
ll w[N];

ll pre[N];

int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        pre[i]=(pre[i-1]+a[i])%mod;
    }
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        w[i]%=mod;
    }
    ll ans=0;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=sum+(pre[n-i+1]-pre[i-1]+mod)%mod;
        sum%=mod;
        ans=ans+(sum*w[i])%mod;
        ans%=mod;
    }
    printf("%lld\n",ans%mod);
    return 0;
}