思路
先考虑 \(\Theta(n^2k)\) 的暴力 DP。
定义 \(dp_{i,j}\) 表示在前 \(i\) 个数中选取 \(j\) 个的最小和，转移显然：
\[dp_{i,j} = \min_{1 \leq k < i}\{dp_{k,j - 1} + s_{k + 1,i} \bmod p\} \]注意到一个性质：\(dp_{i,j} \equiv s_i \pmod p\)。因为前者是前 \(i\) 项分为若干段的模 \(p\) 下的和，与后者显然在模 \(p\) 意义下同余。
对于 \(dp_{i,j}\) 的两个转移的位置 \(k_1,k_2\)，计算出的结果分别是，\(dp_{k_1,j - 1} + s_{k_1 + 1,i} \bmod p\) 与 \(dp_{k_2,j - 1} + s_{k_2 + 1,i} \bmod p\)。并且有：
\[dp_{k_1,j - 1} + s_{k_1 + 1,i} \bmod p \equiv dp_{k_2,j - 1} + s_{k_2 + 1,i} \bmod p \pmod p \]假设 \(dp_{k_1,j - 1} < dp_{k_2,j - 1}\)，由于 \(s_{k_1 + 1,i} \bmod p\) 与 \(s_{k_2 + 1,i} \bmod p\) 一定小于 \(p\)，所以前者一定小于后者。
这样，对于每一个 \(j\)，记录最小的 \(dp_{i,j}\) 即可。
Code
#include <bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N = 5e5 + 10,M = 110;
int n,m,p;
int arr[N],s[N];
int dp[N][M],f[M];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
#define sum(l,r) ((s[r] - s[l - 1]) % p)
signed main(){
n = read(),m = read(),p = read();
for (re int i = 1;i <= n;i++) s[i] = s[i - 1] + (arr[i] = read());
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= min(i,m);j++) dp[i][j] = dp[f[j - 1]][j - 1] + sum(f[j - 1] + 1,i);
for (re int j = 1;j <= min(i,m);j++){
if (!f[j] || dp[f[j]][j] > dp[i][j]) f[j] = i;
}
}
printf("%lld",dp[n][m]);
return 0;
}