ヒント

解説

前提知識として floor_sum アルゴリズム が必要です。このアルゴリズムは整数 \(n,m,a,b\) に対して \(\displaystyle f(n,m,a,b)=\sum_{i=0}^{n-1}\left\lfloor\frac{ai+b}m\right\rfloor\) を \(O(\log m)\) で計算するアルゴリズムです。詳しくは リンク先にある解説 を読んでください。

\(A\) の重複を削除しソートすることで \(A_1 < A_2 < ... < A_N\) が成立しているとします。

\(j\) を固定し、 \(\displaystyle \left\{(Ck+A_j)\ \text{mod}\ M\right\}=\min_{1\le i\le N}\left\{(Ck+A_i)\ \text{mod}\ M\right\}\) となるような \(0\le k < K\) の集合を \(S_j\) とします。 \(j\geq 2\) なら、\(k\in S_j\) となる条件は \(\left\{(Ck+A_{j-1})\ \text{mod}\ M \right\} > \left\{(Ck+A_j)\ \text{mod}\ M \right\}\) と言い換えられ、さらに \(\displaystyle \left\lfloor\frac{Ck+A_{j}}{M} \right\rfloor-\left\lfloor\frac{Ck+A_{j-1}}{M} \right\rfloor=1\) と言い換えることができます。 \(\displaystyle \left\lfloor\frac{Ck+A_{j}}{M} \right\rfloor-\left\lfloor\frac{Ck+A_{j-1}}{M} \right\rfloor\) は \(0\) か \(1\) にしかならないので、\(\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)\) となります。

よって、

\[ \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} \]

となります。一方、 \(j=1\) なら

\[\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\]

となるので、答えは

\[ \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)\) と \(|S_j|\) はどちらも floor_sum を用いて高速に計算できます。

以上でこの問題が解けました。計算量は \(A\) のソートと floor_sum の計算がボトルネックとなり \(O(N(\log N+\log M))\) になります。

実装の際はオーバーフローに注意してください。この問題は、多倍長整数型や 128bit 整数型を使うか、 modint で適当な \(2\) つの素数（例えば \(10^9+7\) と \(10^9+9\) など）で割ったあまりをそれぞれ求め、そこから crt で復元することで回避できます。また、例えば C++ の unsigned long long などではオーバーフローを起こしても \(\text{mod}\ 2^{64}\) で正しい値となることが保証されているので、そのような型を使っても良いです。 AtCoder Library の floor_sum では unsigned long long を使用しており、\(\text{mod}\ 2^{64}\) で正しい答えを返すことが保証されています。

実装例(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)

実装例(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;
}