← 返回题目列表

Codeforces · 958/C3

C3. 加密(硬)

中文机器翻译题面 查看原题

海蒂现在只差一个密码就能破解死星计划的加密。应该向她展示下一个代码描述的屏幕看起来和上一个几乎一样,但谁能想到邪恶的帝国工程师会在这个小屏幕上填满几百万位数字!认为有人会读完它们真是太荒谬了……

Heidi 再次被赋予序列 A 和两个整数 k 和 p。她需要找出加密密钥S是什么。

设 X 为整数序列,p 为正整数。我们将 X 的分数定义为 X 模 p 的元素之和。

给 Heidi 一个由 N 个整数组成的序列 A,并且还给定整数 k 和 p。她的目标是将 A 分成 k 部分,以便:

- 每个部分至少包含 A 的 1 个元素,并且每个部分由 A 的连续元素组成。
- 没有两个部分重叠。
- 这些部分的分数总和 S 被最小化(而不是最大化!)。

输出和S,即加密码。

输入

输入的第一行包含三个空格分隔的整数 N、k 和 p (k ≤ N ≤ 500 000, 2 ≤ k ≤ 100, 2 ≤ p ≤ 100) – 分别是 A 中的元素数量、A 应分为的部分数量以及计算分数的模数。

第二行包含 N 个空格分隔的整数,它们是 A 的元素。每个整数都来自区间 [1, 1 000 000]。

输出

按照问题陈述中的描述输出数字 S。

示例

输入 #1

4 3 10
3 4 7 2

输出 #1

6

输入 #2

10 5 12
16 3 24 13 9 8 7 5 12 12

输出 #2

13

注意

在第一个示例中,如果输入序列被分割为 (3), (4, 7), (2),则总分将为 $$( 3 \bmod { 1 0 } ) + ( 4 + 7 \bmod { 1 0 } ) + ( 2 \bmod { 1 0 } ) = 3 + 1 + 2 = 6$$。很容易看出这个分数是可能的最小分数。

在第二个示例中,获得分数 13 的一种可能方法是进行以下分割:(16, 3), (24), (13), (9, 8), (7, 5, 12, 12)。