← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

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
3
输入 #2
3 20
199 41 299
输出 #2
19
C++ 编辑器
输入
输出