← 返回题目列表

AtCoder · arc182_e

E. 线性模的最小值之和

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

分数: 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