#P13213. [ARC182E] Sum of Min of Mod of Linear

    ID: 12396 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500数学数论模运算排序数据结构并查集

[ARC182E] Sum of Min of Mod of Linear

题目描述

给定正整数 N,M,KN, M, K,非负整数 CC,以及一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)。

请计算 $\displaystyle\sum_{k=0}^{K-1} \min_{1 \leq i \leq N} \{ (Ck + A_i) \bmod M \}$ 的值。

输入格式

输入以以下格式从标准输入读入。

NN MM CC KK A1A_1 A2A_2 …\ldots ANA_N

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 5 3 3
1 3

输出 #1

4

输入输出样例 #2

输入 #2

5 4 3 182
0 3 2 1 2

输出 #2

0

输入输出样例 #3

输入 #3

5 718 651 193855
3 532 44 109 58

输出 #3

29484897

说明/提示

限制条件

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤M≤1091 \leq M \leq 10^9
  • 0≤C<M0 \leq C < M
  • 1≤K≤1091 \leq K \leq 10^9
  • 0≤Ai<M0 \leq A_i < M
  • 所有输入均为整数

样例解释 1

当 k=0k=0 时,{(3k+1) mod 5}=1\{(3k+1)\bmod 5\}=1,{(3k+3) mod 5}=3\{(3k+3)\bmod 5\}=3,所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=1$。
当 k=1k=1 时,{(3k+1) mod 5}=4\{(3k+1)\bmod 5\}=4,{(3k+3) mod 5}=1\{(3k+3)\bmod 5\}=1,所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=1$。
当 k=2k=2 时,{(3k+1) mod 5}=2\{(3k+1)\bmod 5\}=2,{(3k+3) mod 5}=4\{(3k+3)\bmod 5\}=4,所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=2$。
因此,答案为 1+1+2=41+1+2=4,请输出 44。