← 返回题目

题库练习最大模意义下子序列

← 上一题下一题 →

A6277 | $最大模意义下子序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个包含 $n$ 个整数的数组 $a$，以及一个整数 $m$。你需要从中选择若干个下标，组成一个严格递增的下标序列 $$ b_1, b_2, \dots, b_k \quad (1 \le b_1 < b_2 < \dots < b_k \le n), $$ 使得下面这个值尽可能大： $$ \left(\sum_{i=1}^k a_{b_i}\right) \bmod m. $$ 你也可以一个数都不选，此时视为选出的下标序列为空，和为 $0$，取模后的值为 $0$。 请你输出上述表达式可能取得的**最大值**。

输入格式

第一行包含两个整数 $n$ 和 $m$： - $1 \le n \le 35$， - $1 \le m \le 10^9$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，满足： - $1 \le a_i \le 10^9$。

输出格式

输出一个整数，表示 $$ \left(\sum_{i=1}^k a_{b_i}\right) \bmod m $$ 在所有合法选择下标序列的方案中，能够取得的最大值。

输入输出样例

输入 #1

4 4
5 2 4 1

输出 #1

输入 #2

3 20
199 41 299

输出 #2

C++ 编辑器

输入

输出