?

問題 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; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的问题 G: 区间权值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。