Choose Two and Eat One

题目描述

一个盒子里有 $N$ 个球，每个球上写了一个介于 $1$ 到 $M-1$ 之间的整数。 对于 $i = 1, 2, \ldots, N$，第 $i$ 个球上写的整数为 $A_i$。 当盒子中剩下两个或更多球时，Takahashi 会重复以下操作。

首先，任意选择两个球。 然后，得到一个分数，等于 $x^y + y^x$ 被 $M$ 除的余数，其中 $x$ 和 $y$ 是写在这两个球上的整数。 最后，任意选择这两个球中的一个，将其吃掉，并把另一个放回盒子中。

输出 Takahashi 能得到的最大可能的总分。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

4 10
4 2 3 2

20

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

1733

提示

$2 \leq N \leq 500$ $2 \leq M \leq 10^9$ $1 \leq A_i \leq M-1$ 输入中的所有数值都是整数。考虑以下情形。下面，$X \bmod Y$ 表示非负整数 $X$ 被正整数 $Y$ 除的余数。

取出盒子中的第一个和第三个球，得分为 $(4^3 + 3^4) \bmod 10 = 5$ 分。然后，吃掉第一个球并把第三个球放回盒子。此时盒子中有第二、第三和第四个球。 取出第三和第四个球，得分为 $(3^2 + 2^3) \bmod 10 = 7$ 分。然后，吃掉第三个球并把第四个球放回盒子。此时盒子中有第二和第四个球。 取出第二和第四个球，得分为 $(2^2 + 2^2) \bmod 10 = 8$ 分。然后，吃掉第二个球并把第四个球放回盒子。此时盒子中只剩第四个球。

在这里，Takahashi 总共得到 $5 + 7 + 8 = 20$ 分，这个值是可能的最大值。

标签: AtCoder|abc282E

来源

AtCoder|abc282E