设想你现在是班主任,手下掌管着一个班 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 个数之和。