最大子序列模和(Maximum Subsequence)

题目描述

给定一个包含 $n$ 个整数的数组 $a$，以及一个整数 $m$。你需要选择若干个索引序列 $b_1, b_2, \dots, b_k$（$1 \le b_1 < b_2 < \dots < b_k \le n$），使得下式的值最大化：

$\left(\sum\limits_{i=1}^k a_{b_i}\right) \bmod m$

你可以选择的序列也可以为空。

请输出上述表达式可能取得的最大值。

输入格式

第一行包含两个整数 $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}$）。

输出格式

输出上述表达式可能取得的最大值。

样例输入 #1

4 4
5 2 4 1

样例输出 #1

3

样例输入 #2

3 20
199 41 299

样例输出 #2

19

数据范围

在第一个样例中，你可以选择序列 $b = \{1, 2\}$，这样 $\sum a_{b_i} = 7$（模 $4$ 之后为 $3$，其值最大）。

在第二个样例中，你可以选择序列 $b = \{3\}$。

由 ChatGPT 5 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接