CF958C3 Encryption (hard)

Heidi 现在只差一个代码就能破解死星计划的加密了。应该显示下一个代码描述的屏幕看起来几乎和之前的一样，谁能想到邪恶帝国的工程师会在这个小屏幕上塞下几百万位数字！简直荒谬，谁会去读完这些数字呢…… Heidi 再次得到了一个序列 $A$ 和两个整数 $k$ 与 $p$。她需要找出加密密钥 $S$。 设 $X$ 是一个整数序列，$p$ 是一个正整数。我们定义 $X$ 的分数为 $X$ 所有元素之和对 $p$ 取模的结果。 Heidi 得到一个包含 $N$ 个整数的序列 $A$，还给出了整数 $k$ 和 $p$。她的目标是将 $A$ 分成 $k$ 段，使得： - 每一段至少包含 $1$ 个 $A$ 的元素，并且每一段由 $A$ 的连续元素组成。 - 各段之间没有重叠。 - 这些段的分数之和 $S$ 最小（不是最大！）。 请输出分数之和 $S$，这就是加密代码。

输入的第一行包含三个用空格分隔的整数 $N$、$k$ 和 $p$（$k \leq N \leq 500000$，$2 \leq k \leq 100$，$2 \leq p \leq 100$）——表示 $A$ 的元素个数，需要分成的段数，以及计算分数时取模的值。 第二行包含 $N$ 个用空格分隔的整数，表示序列 $A$ 的元素。每个整数都在区间 $[1,1000000]$ 内。

输出题目描述中要求的分数之和 $S$。

在第一个样例中，如果将输入序列分为 $(3)$、$(4,7)$、$(2)$，总分数为 $3 + (4+7) \bmod 5 + 2 = 3 + 1 + 2 = 6$。很容易看出这是最小的分数。 在第二个样例中，一种得到分数 $13$ 的分法是：$(16,3)$、$(24)$、$(13)$、$(9,8)$、$(7,5,12,12)$。 由 ChatGPT 4.1 翻译