1650 - 前缀最小值

题目描述

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

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

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

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

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

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

输入

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

输出

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

样例

输入

5 666

输出

1650
说明

【样例解释】

数列为 666,304,692,188,596,前缀最小值为666,304,304,188,188,和为 1650

来源

动态规划

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


上一题 下一题