题意 : 给出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; }