题解：CF958C3 Encryption (hard)

显然 DP。设 f(i, j) 表示考虑前 i 个数，划分成 j 段的答案。

令 s_i = (a_1+a_2+\dots + a_i) \bmod p。转移 f(k,j-1) + (s_i-s_k) \bmod p \to f(i, j)。

注意到 s_i - s_k = \begin{cases} s_i - s_k & s_i \ge s_k \\ s_i - s_k + p & s_i < s_k \end{cases}。于是可以把 DP 式子重写：

开两个树状数组。第一个维护所有满足 s_k \le s_i 的 f(i,j-1)-s_k 的最小值，第二个维护所有满足 s_k \ge s_i+1 的 f(i,j-1)-s_k 的最小值。转移就可以优化到 \log p 了。

复杂度 \mathcal O(nm\log p)。需要卡常，比如把 int 换成 short。

// Problem: 
//     Encryption (hard)
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF958C3
// Memory Limit: 500 MB
// Time Limit: 2200 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #define tests
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int n, m, p;
int a[N];
short f[N][110];

inline int min(const int a, const int b) {
    return a < b ? a : b;
}

struct Tree1 {
    short tr[110];
    void clear() { memset(tr, 0x3f, sizeof tr); }

    void modify(short x, short d) {
        x ++ ;
        for (short i = x; i < 110; i += i & -i) tr[i] = min(tr[i], d);
    }

    short query(short x) {
        x ++ ;
        short res = 32767;
        for (short i = x; i; i -= i & -i) res = min(res, tr[i]);
        return res;
    }
}T1;

struct Tree2 {
    short tr[110];
    void clear() { memset(tr, 0x3f, sizeof tr); }

    void modify(short x, short d) {
        x = 110 - x;
        for (short i = x; i < 110; i += i & -i) tr[i] = min(tr[i], d);
    }

    short query(short x) {
        x = 110 - x;
        short res = 32767;
        for (short i = x; i; i -= i & -i) res = min(res, tr[i]);
        return res;
    }
}T2;

void solve() {
    cin >> n >> m >> p;

    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        a[i] = (a[i] + a[i - 1]) % p;
        f[i][1] = a[i];
    }

    for (short j = 2; j <= m; ++ j ) {
        T1.clear(), T2.clear();

        T1.modify(a[0], f[0][j - 1] - a[0]);
        T2.modify(a[0], f[0][j - 1] - a[0]);
        for (int i = 1; i <= n; ++ i ) {
            f[i][j] = i >= j ? a[i] + min(T1.query(a[i]), T2.query(a[i] + 1) + p) : 32767;
            T1.modify(a[i], f[i][j - 1] - a[i]);
            T2.modify(a[i], f[i][j - 1] - a[i]);
        }
    }

    cout << f[n][m] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
#ifdef tests
    cin >> T;
#endif
    while (T -- ) solve();
    return 0;
}