Hints

Editorial

As a prerequisite, you need the floor_sum algorithm. This algorithm calculates \(\displaystyle f(n,m,a,b)=\sum_{i=0}^{n-1}\left\lfloor\frac{ai+b}m\right\rfloor\) in \(O(\log m)\) time. Please read the explanation in the linked article for more details.

Let’s assume that \(A\) has been sorted and duplicates removed so that \(A_1 < A_2 < ... < A_N\) holds.

Fix \(j\), and let \(S_j\) be the set of \(0\le k < K\) such that \(\displaystyle \left\{(Ck+A_j)\ \text{mod}\ M\right\}=\min_{1\le i\le N}\left\{(Ck+A_i)\ \text{mod}\ M\right\}\). If \(j\geq 2\), the condition for \(k\in S_j\) can be rephrased as \(\left\{(Ck+A_{j-1})\ \text{mod}\ M \right\} > \left\{(Ck+A_j)\ \text{mod}\ M \right\}\), and further as \(\displaystyle \left\lfloor\frac{Ck+A_{j}}{M} \right\rfloor-\left\lfloor\frac{Ck+A_{j-1}}{M} \right\rfloor=1\). Since \(\displaystyle \left\lfloor\frac{Ck+A_{j}}{M} \right\rfloor-\left\lfloor\frac{Ck+A_{j-1}}{M} \right\rfloor\) can only be \(0\) or \(1\), we have \(\displaystyle |S_j|=\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+A_{j}}{M} \right\rfloor-\left\lfloor\frac{Ck+A_{j-1}}{M} \right\rfloor\right)\).

Therefore,

\[ \begin{aligned} &\phantom{=}\sum_{k\in S_j}\min_{1\le i\le N}\left\{(Ck+A_i)\ \text{mod}\ M \right\}-\sum_{k \in S_j} \left\{(Ck+A_1)\ \text{mod}\ M \right\}\\ &=\sum_{k \in S_j}\left(\left\{(Ck+A_j)\ \text{mod}\ M \right\} - \left\{(Ck+A_1)\ \text{mod}\ M \right\}\right)\\ &=\sum_{k \in S_j} (A_j-A_1-M)\\ &=-(M+A_1-A_j)|S_j| \end{aligned} \]

Meanwhile, for \(j=1\), we have

\[\sum_{k\in S_j}\min_{1\le i\le N}\left\{(Ck+A_i)\ \text{mod}\ M \right\}-\sum_{k \in S_j} \left\{(Ck+A_1)\ \text{mod}\ M \right\}=0\]

Thus, the answer is

\[ \begin{aligned} &\phantom{=}\sum_{k=0}^{K-1}\min_{1\le i\le N}\left\{(Ck+A_i)\ \text{mod}\ M \right\}\\ &=\sum_{j=1}^N\sum_{k\in S_j}\left\{(Ck+A_j)\ \text{mod}\ M \right\}\\ &=\sum_{j=1}^N\sum_{k \in S_j} \left\{(Ck+A_1)\ \text{mod}\ M \right\} -\sum_{j=2}^N(M+A_1-A_j)|S_j|\\ &=\sum_{k=0}^{K-1} \left\{(Ck+A_1)\ \text{mod}\ M \right\}-\sum_{j=2}^N (M+A_1-A_j)|S_j| \end{aligned} \]

\(\displaystyle \sum_{k=0}^{K-1} \left\{(Ck+A_1)\ \text{mod}\ M \right\}=\sum_{k=0}^{K-1}\left(Ck+A_1-M\left\lfloor\frac{Ck+A_1}M \right\rfloor\right)\) and \(|S_j|\) can both be calculated quickly using the floor_sum algorithm.

Now, the problem is solved. The complexity is \(O(N(\log N+\log M))\), with the bottlenecks being the sorting of \(A\) and the calculation of floor_sum.

Be careful with overflow during implementation. You can avoid this issue by using multi-precision integers, 128-bit integers, or by using a modint with two different primes (e.g., \(10^9+7\) and \(10^9+9\)) and reconstructing the result using CRT. Alternatively, you can use a type like C++’s unsigned long long, which guarantees that the correct value modulo \(2^{64}\) is returned even in case of overflow. The AtCoder Library’s floor_sum uses unsigned long long and guarantees the correct answer modulo \(2^{64}\).

Sample Implementation (Python3)

from atcoder.math import floor_sum
n, m, c, k = map(int, input().split())
a = sorted(list(set(map(int, input().split()))))
n = len(a)
fl = [floor_sum(k, m, c, a[i]) for i in range(n)]
ans = c * k * (k - 1) // 2 + k * a[0] - m * fl[0]
for i in range(1, n):
  ans -= (m + a[0] - a[i]) * (fl[i] - fl[i - 1])
print(ans)

Sample Implementation (C++)

#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;
#define ull unsigned long long
int main() {
    ull n, m, c, k;
    cin >> n >> m >> c >> k;
    vector<ull> a(n);
    for (ull& i : a) cin >> i;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = a.size();
    vector<ull> fl(n);
    for (int i = 0; i < n; i++) {
        fl[i] = atcoder::floor_sum(k, m, c, a[i]);
    }
    ull ans = k * (k - 1) / 2 * c + k * a[0] - m * fl[0];
    for (int i = 1; i < n; i++) {
        ans -= (m + a[0] - a[i]) * (fl[i] - fl[i - 1]);
    }
    cout << ans << endl;
}