链接:https://www.nowcoder.com/acm/contest/204/G
来源:牛客网
题目描述
小 Bo 有 n 个正整数 a1…an,以及一个权值序列 w1…wn,现在他定义
现在他想知道 的值,需要你来帮帮他
你只需要输出答案对 109+7 取模后的值
输入描述:
第一行一个正整数 n
第二行 n 个正整数 a1…an
第三行 n 个正整数 w1…wn
输出描述:
输出答案对 109+7 取模后的值
示例1
输入
复制
3
1 1 1
1 1 1
输出
复制
10
备注:
1≤ n≤ 3x 105
1≤ ai≤ 107
1≤ wi≤ 107
感觉很经典的题
双重的前缀和
用的方法和题解不太一样,题解是直接推出一个式子…
我的方法是先预处理a的前缀和和w的前缀和,对于w1来说,也就是区间是1的所有a的和再乘w1,对于w2来说,a1就需要乘一次,a2需要两次这样子
比如现在n=5
a1 a2 a3 a4 a5
1 1 1 1 1 w1(即区间为1的覆盖)
1 2 2 2 1 w2
1 2 3 2 1 w3
1 2 2 2 1 w4
1 1 1 1 1 w5
这样就看出了一点规律,对称的,然后我们如果枚举w,肯定没办法再枚举a,所以每一行的和就得考虑预处理出来,比如第一行,就是pa[n](a的前缀和)-pn[0],然后第二行就在第一行的基础上加上pa[n-1]-pn[1]这样子,这样也可以在On预处理出每一行的和,然后直接乘以w就好了
代码:
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
const int N=300050;
const ll MOD=1e9+7;
ll a[N],w[N];
ll pa[N],pw[N];
ll pf[N];
int main(void){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
pa[i]=(pa[i-1]+a[i])%MOD;
}
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
pw[i]=(pw[i-1]+w[i])%MOD;
}
//层
int s=0,t=n;
pf[1]=pa[t]-pa[s];
s++;
t--;
for(int i=2;i<=(n+1)/2;i++){
//printf("%d %d\n",s,t);
pf[i]=(pf[i-1]+(pa[t]-pa[s]))%MOD;
s++;
t--;
}
for(int i=(n+1)/2+1;i<=n;i++){
pf[i]=pf[n-i+1];
}
// for(int i=1;i<=n;i++){
// printf("%lld ",pf[i]);
// }
// printf("\n");
ll ans=0;
//枚举w
for(int i=1;i<=n;i++){
ans=(ans+w[i]*pf[i])%MOD;
}
printf("%lld\n",ans);
return 0;
}