公式解説を前提にします。

\(A_i, A_{L+i}, A_{2L+i}, \cdots\) を \(M\) で割った余りをすべて \(k\) にするとき、操作回数の最小値 \(f_{i,k}\) は

\[ f_{i,k} = \sum_{j} ((k - A_{Lj+i}) \bmod M) \]

で表されます。制約から \(0 \le A_{Lj+i} \lt M\) であるので、

\[ (k-A_{Lj+i}) \bmod M = \begin{cases} k-A_{Lj+i} & (k \ge A_{Lj+i})\\ k-A_{Lj+i}+M & (k \lt A_{Lj+i}) \end{cases} \]

です。

よって \(A_i, A_{L+i}, A_{2L+i}, \cdots\) が全体で \(s\) 個、 \(k \lt A_{Lj+i}\) となるものの個数が \(t\) 個あるとしたとき、式を整理すると

\[ f_{i,k} = ks + Mt - \sum_{j} A_{Lj+i} \]

となります。これを観察すると、 \(k\) が大きくなるにつれ \(t\) が広義単調減少していきます。しかし、 \(t\) の変化点は高々 \(s\) 種類しかありません。それ以外の場所では、 \(f_{i,k+1} = f_{i,k} + s\) です。

イメージを図で表すと以下になっています。

（ここに図があるはずですがリンク切れしていたら教えて下さい）

DPの遷移のときには、実はすべての \(k\) で遷移する必要はなく、

図の各緑点 （\(A_{Lj+i}\) のとりうる値）で各 \(j=0,1,\cdots, M-1\) に対して \(dp_{i,((j+k) \bmod M)} \leftarrow \min(dp_{i,((j+k)\bmod M)}, dp_{i-1,j}+f_{i,k})\) と遷移して、すべての遷移が終わった最後に \(j=0,1,\cdots, 2M-1\) の順に \(dp_{i,(j+1)\bmod M} \leftarrow \min(dp_{i,(j+1)\bmod M}, dp_{i,j \bmod M} + s)\) とすると同じ遷移ができます。

これを \(i=1,2,\cdots, L\) の順に行えばよいです。

各 \(k=A_{Lj+i}\) に対する \(f_{i,k}\) の値の取得は \(A_i, A_{L+i}, A_{2L+i}, \cdots\) をソートすると簡単に行えます。このときに、std::sortなどを用いると問題の時間計算量は全体で \(O(NM \log N)\) となります。

しかし、この問題の制約から \(0 \le A_x < M\) であるので、バケットソートを用いることで時間・空間計算量 \(O(LM+N)\) ですべての \(i=1,2,\cdots, L\) に対して \(A_i, A_{L+i}, A_{2L+i}, \cdots\) のソートを行うことができ、 \(O(NM)\) 時間が達成できます。

実装例(C++, 4ms)