\(A\) のすべての長さ \(L\) の連続部分列の総和が \(M\) の倍数であることは、以下の条件をともに満たすことと同値です。

• \(A_1 + A_2 + \ldots + A_L\) が \(M\) の倍数
• \(1 \leq i \leq N - L\) なる任意の \(i\) について \(A_i - A_{i + L}\) が \(M\) の倍数

このことから、\(A_1, A_2, \ldots, A_L\) への操作回数がわかっているとき、\(i = L + 1, L + 2, \ldots, N\) について \(A_i\) への操作回数は \(A_{i - L}\) と \(A_i\) を \(M\) で割った余りが等しくなるような最小の回数であることがわかります。

\(f_{i, j}\) を \(A_i, A_{L + i}, A_{2L + i}, \ldots\) を \(M\) で割った余りがすべて \(j\) になるために必要な操作回数の最小値とします。これは愚直に \(O(NM)\) 時間で計算が可能です。

\(f_{i, j}\) の値を利用して dp による計算を行います。

\(dp_{i,j}\) を \(A_1, A_2, \ldots, A_i\) までの操作回数を確定させて、\(A_1 + A_2 + \ldots, A_i\) を \(M\) で割った余りが \(j\) であるときの操作回数の最小値として定めます。ただし、ここでの操作回数の最小値とは、\(A_1, A_2, \ldots, A_i\) に対するものだけではなく、添え字を \(L\) で割った余りが \(1, 2, \ldots, i\) （を \(L\) で割った余り）と等しい要素全体への操作回数について考えます。上の議論から、\(A_i\) に対する操作回数を決めたとき、\(A_{L + i}, A_{2L + i}, \ldots\) に対する操作回数も決まるので、このような計算が行えます。

具体的な dp の遷移について解説します。\(A_i\) を \(M\) で割った余りを \(k\) にさせると決めたとき、\(A_i, A_{L + i}, A_{2L + i}, \ldots\) に対する操作回数の最小値は（その定義から）\(f_{i, k}\) です。したがって、\(dp_{i, ((j + k) \bmod M)} \leftarrow \min(dp_{i, ((j + k) \bmod M)}, dp_{i - 1, j} + f_{i, k})\) として dp の計算を行うことができます。最終的な答えは \(dp_{L, 0}\) です。

dp の計算は全体として \(O(LM^2)\) 時間で行え、これは適切な実装のもと十分高速です。

Bonus : \(O(NM)\) 時間で解けます。

実装例

#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000001;
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }

int main() {
	int n, m, l;
	cin >> n >> m >> l;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> dp(m, inf);
	dp[0] = 0;
	for (int i = 0; i < l; i++) {
		vector<int> ep(m, inf);
		for (int j = 0; j < m; j++) {
			int cost = 0;
			for (int k = i; k < n; k += l) {
				if (j >= a[k]) cost += j - a[k];
				else cost += j - a[k] + m;
			}
			for (int k = 0; k < m; k++) chmin(ep[(k + j) % m], dp[k] + cost);
		}
		dp = move(ep);
	}
	cout << dp[0] << '\n';
}