分数: 800 点
问题陈述
给你正整数 N, M, K,一个非负整数 C,以及一个整数序列 A=(A_1, A_2, \ldots, A_N) 长度 N.
查找 \displaystyle \sum_{k=0}^{K-1}\min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace.
约束
- 1 \le N \le 10^5
- 1 \le M \le 10^9
- 0 \le C < M
- 1 \le K \le 10^9
- 0 \le A_i < M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M C K A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
2 5 3 3 1 3
示例输出 1
4
对于 k=0, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=1 和 \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=3,所以 \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=1.
对于 k=1, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=4 和 \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=1,所以 \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=1.
对于 k=2, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=2 和 \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=4,所以 \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=2.
因此,答案是 1+1+2=4。因此,打印 4.
示例输入 2
5 4 3 182 0 3 2 1 2
示例输出 2
0
示例输入 3
5 718 651 193855 3 532 44 109 58
示例输出 3
29484897