English · Original
Chinese · Translation
Formal · Original
Heidi is now just one code away from breaking the encryption of the Death Star plans. The screen that should be presenting her with the description of the next code looks almost like the previous one, though who would have thought that the evil Empire engineers would fill this small screen with several million digits! It is just ridiculous to think that anyone would read them all...
Heidi is once again given a sequence _A_ and two integers _k_ and _p_. She needs to find out what the encryption key _S_ is.
Let _X_ be a sequence of integers, and _p_ a positive integer. We define the score of _X_ to be the sum of the elements of _X_ modulo _p_.
Heidi is given a sequence _A_ that consists of _N_ integers, and also given integers _k_ and _p_. Her goal is to split _A_ into _k_ parts such that:
* Each part contains at least 1 element of _A_, and each part consists of contiguous elements of _A_.
* No two parts overlap.
* The total sum _S_ of the scores of those parts is **minimized** (not maximized!).
Output the sum _S_, which is the encryption code.
## Input
The first line of the input contains three space-separated integers _N_, _k_ and _p_ (_k_ ≤ _N_ ≤ 500 000, 2 ≤ _k_ ≤ 100, 2 ≤ _p_ ≤ 100) – the number of elements in _A_, the number of parts _A_ should be split into, and the modulo for computing scores, respectively.
The second line contains _N_ space-separated integers that are the elements of _A_. Each integer is from the interval \[1, 1 000 000\].
## Output
Output the number _S_ as described in the problem statement.
[samples]
## Note
In the first example, if the input sequence is split as (3), (4, 7), (2), the total score would be . It is easy to see that this score is the smallest possible.
In the second example, one possible way to obtain score 13 is to make the following split: (16, 3), (24), (13), (9, 8), (7, 5, 12, 12).
Heidi 现在只差一步就能破解死星计划的加密了。本应向她展示下一个密码说明的屏幕，看起来几乎和上一个一模一样，但谁能想到邪恶的帝国工程师竟会将这小小的屏幕填满数百万位数字！指望任何人去阅读所有这些数字，简直是荒谬的...
Heidi 再次获得一个序列 #cf_span[A] 以及两个整数 #cf_span[k] 和 #cf_span[p]。她需要找出加密密钥 #cf_span[S]。
令 #cf_span[X] 为一个整数序列，#cf_span[p] 为一个正整数。我们定义 #cf_span[X] 的 #cf_span(class=[tex-font-style-underline], body=[score]) 为 #cf_span[X] 中所有元素之和对 #cf_span[p] 取模的结果。
Heidi 被给定一个包含 #cf_span[N] 个整数的序列 #cf_span[A]，以及整数 #cf_span[k] 和 #cf_span[p]。她的目标是将 #cf_span[A] 分成 #cf_span[k] 个部分，使得：
请输出加密密钥 #cf_span[S]。
输入的第一行包含三个用空格分隔的整数 #cf_span[N], #cf_span[k] 和 #cf_span[p]（#cf_span[k ≤ N ≤ 500 000], #cf_span[2 ≤ k ≤ 100], #cf_span[2 ≤ p ≤ 100]）——分别表示序列 #cf_span[A] 的元素个数、需要划分的子段数，以及计算得分时使用的模数。
第二行包含 #cf_span[N] 个用空格分隔的整数，表示序列 #cf_span[A] 的元素。每个整数均在区间 #cf_span[[1, 1 000 000]] 内。
请输出如题所述的数字 #cf_span[S]。
在第一个示例中，若输入序列被划分为 #cf_span[(3)], #cf_span[(4, 7)], #cf_span[(2)]，则总得分为 。可以轻易看出，这是可能的最小得分。
在第二个示例中，一种获得得分 #cf_span[13] 的可能划分方式为：#cf_span[(16, 3)], #cf_span[(24)], #cf_span[(13)], #cf_span[(9, 8)], #cf_span[(7, 5, 12, 12)]。
## Input
输入的第一行包含三个用空格分隔的整数 #cf_span[N], #cf_span[k] 和 #cf_span[p]（#cf_span[k ≤ N ≤ 500 000], #cf_span[2 ≤ k ≤ 100], #cf_span[2 ≤ p ≤ 100]）——分别表示序列 #cf_span[A] 的元素个数、需要划分的子段数，以及计算得分时使用的模数。第二行包含 #cf_span[N] 个用空格分隔的整数，表示序列 #cf_span[A] 的元素。每个整数均在区间 #cf_span[[1, 1 000 000]] 内。
## Output
请输出如题所述的数字 #cf_span[S]。
[samples]
## Note
在第一个示例中，若输入序列被划分为 #cf_span[(3)], #cf_span[(4, 7)], #cf_span[(2)]，则总得分为 。可以轻易看出，这是可能的最小得分。在第二个示例中，一种获得得分 #cf_span[13] 的可能划分方式为：#cf_span[(16, 3)], #cf_span[(24)], #cf_span[(13)], #cf_span[(9, 8)], #cf_span[(7, 5, 12, 12)]。
**Definitions**
Let $ N, k, p \in \mathbb{Z}^+ $ be given integers.
Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of integers, where $ a_i \in [1, 10^6] $.
A **partition** of $ A $ into $ k $ contiguous non-empty parts is a sequence of indices $ 0 = i_0 < i_1 < i_2 < \dots < i_k = N $, defining $ k $ subsequences:
$ X_j = (a_{i_{j-1}+1}, a_{i_{j-1}+2}, \dots, a_{i_j}) $ for $ j = 1, 2, \dots, k $.
The **score** of a part $ X_j $ is defined as:
$$
\text{score}(X_j) = \left( \sum_{x \in X_j} x \right) \bmod p
$$
The **total score** $ S $ of a partition is the sum of the scores of all parts:
$$
S = \sum_{j=1}^k \text{score}(X_j)
$$
**Constraints**
1. $ k \leq N \leq 500{,}000 $
2. $ 2 \leq k \leq 100 $
3. $ 2 \leq p \leq 100 $
4. $ 1 \leq a_i \leq 1{,}000{,}000 $ for all $ i \in \{1, \dots, N\} $
**Objective**
Find the **minimum possible total score** $ S $ over all valid partitions of $ A $ into exactly $ k $ contiguous parts.
API Response (JSON)
{
"problem": {
"name": "C3. Encryption (hard)",
"description": {
"content": "Heidi is now just one code away from breaking the encryption of the Death Star plans. The screen that should be presenting her with the description of the next code looks almost like the previous one,",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF958C3"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Heidi is now just one code away from breaking the encryption of the Death Star plans. The screen that should be presenting her with the description of the next code looks almost like the previous one,...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Heidi 现在只差一步就能破解死星计划的加密了。本应向她展示下一个密码说明的屏幕，看起来几乎和上一个一模一样，但谁能想到邪恶的帝国工程师竟会将这小小的屏幕填满数百万位数字！指望任何人去阅读所有这些数字，简直是荒谬的...\n\nHeidi 再次获得一个序列 #cf_span[A] 以及两个整数 #cf_span[k] 和 #cf_span[p]。她需要找出加密密钥 #cf_span[S]。\n\n令 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ N, k, p \\in \\mathbb{Z}^+ $ be given integers. \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of integers, where $ a_i \\in [1, 10^6] $. \n\nA **partition** of $ A $ into $ k ...",
"is_translate": false,
"language": "Formal"
}
]
}