3702 - 一道看似简单的排序题
描述

设想你现在是班主任,手下掌管着一个班 n 位同学,每位同学有一个考试成绩。现在要把他们按成绩排序,排序方式是考试成绩高的同学优先排在前面。
现在校长让你给出你们班排名前 m 的同学的考试成绩之和。
不过这道题的输入方式有点不一般:题目不会直接给出所有成绩,而是给出递推式。设第 i 位同学的考试成绩为 x[i],其中 x[0] = x0,x[i] = (x[i-1] * a + b) mod p(1 <= i <= n)。

输入

第一行两个整数 n, m。
第二行四个整数 x0, a, b, p。

输出

一行一个整数表示排名前 m 的同学的考试成绩之和。

样例

输入

3 2
1 1 1 10

输出

7

输入

4 3
1 1 1 4

输出

6

输入

3 1
1 1 1 1

输出

0
提示

数据范围较大,直接比较排序会超时,可用基数排序。本质上就是求生成序列中最大的 m 个数之和。

来源
51nod 3087
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1