题解：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 式子重写：

$$
\begin{aligned}
f(i,j)&=\min_{k=0}^{i-1} f(k,j-1) + (s_i-s_k) \bmod p \\ &=
s_i + \min_{k=0}^{i-1} f(k,j-1) - s_k + [s_i \ge s_k]p
\end{aligned}
$$

开两个树状数组。第一个维护所有满足 $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`。

```cpp
// 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;
}
```

正在渲染内容...