?

問題 G: 區間權值

時間限制: 1 Sec??內存限制: 128 MB
提交: 112??解決: 49
[提交] [狀態] [討論版] [命題人:admin]

題目描述

小Bo有n個正整數a1..an，以及一個權值序列w1…wn，現在他定義
現在他想知道的值，需要你來幫幫他
你只需要輸出答案對109+7取模后的值

?

輸入

第一行一個正整數n
第二行n個正整數a1..an
第三行n個正整數w1..wn
1≤n≤3×105
1≤ai≤107
1≤wi≤107

?

輸出

輸出答案對109+7取模后的值

?

樣例輸入

3
1 1 1
1 1 1

?

樣例輸出

10

方法：因為要將每一個區間的和加起來再與w相乘，所以可以求出對應的區間和。

AC代碼

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)3e5 + 5;
const ll mod = 1e9+7;
ll a[maxn];
ll w[maxn];
ll suma[maxn];
ll sumaa[maxn];
int main() 
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);ll n;cin>>n;rep(i,1,n) {cin>>a[i];suma[i]=suma[i-1]+a[i];    //求出a數組的前綴和}rep(i,1,n) {cin>>w[i];}int start=0,end=n;sumaa[1]=(suma[end]-suma[start])%mod;      //求出區間為1的所有區間的和start++;end--;int j;for(j=2;j<=(n+1)/2;j++){sumaa[j]=(sumaa[j-1]+suma[end]-suma[start])%mod;     //可以推導出如區間為2的所有區間和等于區間為1的區間和加上a[2]到a[n-1]的和，以此類推start++;end--;}for(;j<=n;j++)sumaa[j]=sumaa[n-j+1];    //區間為n的區間和與區間為1的區間和相等，一次類推ll ans=0;rep(i,1,n) {ans=(ans+(w[i]*sumaa[i])%mod)%mod;}cout<<ans<<endl;return 0;
}

?