区间权值
区间权值
https://ac.nowcoder.com/acm/problem/19798
把式子拆分之后可以发现,它是在区间长度为1-n的范围内求各种前缀和,可以用一些例子分析一下怎么计算
如果n为6
(对号代表要加上这些a[i])
可以发现,随着范围增加,会多出一部分的值,可以用 sum[n-i+1]-sum[i-1]来算这些多出的值(sum[i]代表前缀和)
再继续往后的时候,会倒过来,4和3一样,5和2一样,6和1一样
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #define inf 0x3f3f3f3f #define mod 1000000007 using namespace std; #define _int __int128_t inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return f*x; } void print(int x) { if(x < 0) {putchar('-');x = -x;} if(x/10) print(x/10); putchar(x%10+'0'); } ll n,m,a[300006],w[300006],sum[300006]; int main () { int T,i,t,j,k,p; cin>>n; for(i=1;i<=n;++i){ a[i]=read(); sum[i]=(sum[i-1]+a[i])%mod; } for(i=1;i<=n;++i) w[i]=read(); ll res=0,ans=0; for(i=1;i<=n;++i){ res+=sum[n-i+1]-sum[i-1]+mod; res%=mod; ans=(ans+res*w[i]%mod)%mod; } cout<<ans<<endl; return 0; }