电商网站充值消费系统,wordpress下载页制作,公司网站建设需要注意的地方,wordpress+HTML5游戏问题 G: 区间权值
时间限制: 1 Sec 内存限制: 128 MB 提交: 112 解决: 49 [提交] [状态] [讨论版] [命题人:admin] 题目描述
小Bo有n个正整数a1..an#xff0c;以及一个权值序列w1…wn#xff0c;现在他定义 现在他想知道的值#xff0c;需要你来帮帮他 你只需要输出答案…
问题 G: 区间权值
时间限制: 1 Sec 内存限制: 128 MB 提交: 112 解决: 49 [提交] [状态] [讨论版] [命题人:admin] 题目描述
小Bo有n个正整数a1..an以及一个权值序列w1…wn现在他定义 现在他想知道的值需要你来帮帮他 你只需要输出答案对1097取模后的值 输入
第一行一个正整数n 第二行n个正整数a1..an 第三行n个正整数w1..wn 1≤n≤3×105 1≤ai≤107 1≤wi≤107 输出
输出答案对1097取模后的值 样例输入
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 il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)3e5 5;
const ll mod 1e97;
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;cinn;rep(i,1,n) {cina[i];suma[i]suma[i-1]a[i]; //求出a数组的前缀和}rep(i,1,n) {cinw[i];}int start0,endn;sumaa[1](suma[end]-suma[start])%mod; //求出区间为1的所有区间的和start;end--;int j;for(j2;j(n1)/2;j){sumaa[j](sumaa[j-1]suma[end]-suma[start])%mod; //可以推导出如区间为2的所有区间和等于区间为1的区间和加上a[2]到a[n-1]的和以此类推start;end--;}for(;jn;j)sumaa[j]sumaa[n-j1]; //区间为n的区间和与区间为1的区间和相等一次类推ll ans0;rep(i,1,n) {ans(ans(w[i]*sumaa[i])%mod)%mod;}coutansendl;return 0;
}
