区间权值 | 前缀和
区间权值
https://ac.nowcoder.com/acm/problem/19798
题目思路
首先注意到这个式子表示的含义即为，所有区间的区间和*区间长度的累加和
把式子拆开:
设a数组的前缀和是fa,b数组的前缀和是fb
( fb(r)-fa(l) )* b_(r-l) = fa(r)*b_(r-l) - fa(l)*b_(r-l)
所以说我们可以枚举每个点作为左端点的贡献和右端点的贡献
作为左端点的贡献的即为:-fa(i)*fb(n-i)
作为右端点的贡献即为：fa(i)*fb(i)
枚举顺序统计即可:
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =1e6+10;
const int mod=1e9+7;
const int Mod = 1e9+7;
///const double eps=1e-10;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p,S,T;
ll a[maxn],b[maxn];
ll fa[maxn],fb[maxn];
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
fa[i] = (fa[i-1] + a[i])%mod;
}
for(int i=1;i<=n;i++){
read(b[i]);
fb[i] = (fb[i-1] + b[i])%mod;
}
ll ans = 0,temp = 0;
///(f(r) - f(l))*w(r-l)
///f(r)*w(r-l) - f(l)*w(r-l)
for(int i=1;i<=n;i++){
ans = (ans + (fa[i]*fb[i]))%mod;///right
ans = (ans - (fa[i]*fb[n-i])%mod+mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
/**
1 1 1
1 2 2
2 2 1
1 3 3
2 3 2
3 3 1
**/
投递CVTE等公司9个岗位 >