1649 - 前缀最大值

题目描述

求一个数列的所有前缀最大值之和。

即:给出长度为 n 的数列 a_i,求出对于所有 1≤i≤nmax(a_1,a_2,...,a_i) 的和。

比如,有数列:666 304 692 188 596,前缀最大值为:666 666 692 692 692,和为 3408

对于每个位置的前缀最大值解释如下:对于第 1 个数 666 ,只有一个数,一定最大;对于第 2 个数,求出前两个数的最大数,还是 666 ;对于第 3 个数,求出前 3 个数的最大数是692…… 其余位置依次类推,最后求前缀最大值得和。

由于读入较大,数列由随机种子生成。

其中 a[1]=xa[i]=(379 \times a[i-1]+131) \mod 997。(mod 代表求余数)

输入

一行两个正整数 n, x ,分别表示数列的长度和随机种子。(n ≤ 100000,x < 997)

输出

一行一个正整数表示该数列的前缀最大值之和。

样例

输入

5 666

输出

3408
说明

样例解释

数列为 {666,304,692,188,596},前缀最大值为{666,666,692,692,692},和为 3408

来源

动态规划

标签
题目参数
时间限制 1 秒
内存限制 16 MB
提交次数 3764
通过人数 2577
金币数量 1 枚
难度 入门


上一题 下一题