CF958C3 Encryption (hard)

神仙题，带模分段dp。

题目

一段长为$n$的数列，划分成$k$段，每一段的的价值是这一段的数值和对$p$取模，求这k段的价值和的最小值。

$n \le 500000$，$k,p\le 100$

Solution

思路1

首先$O(nkp)$的做法非常好想，但是没有前途，有前途的暴力反倒是看起来更没有前途的$O(n^2k)$，考虑这种做法的本质思路，发现剪枝重点在枚举分界点上（于是以为是四边形不等式，继续浪费时间），考虑怎样迅速确定分界点，记$sum_i=\sum_{j=1}^ia_j$，$f_{i,j} \equiv sum_i \pmod p$，而我们令目前找出来的两个位置分别为$x$和$y$，那么分别有：
$$
\begin{aligned}
f_{i,j}=f_{x,j-1}+(sum_i-sum_x) \% p \\
f_{i,j}=f_{y,j-1}+(sum_i-sum_y) \% p
\end{aligned}
$$
而对于任意$x,y$，都有：
$$
\begin{aligned}
f_{x,j-1}-sum_x \equiv 0 \pmod p \\
f_{y,j-1}-sum_y \equiv 0 \pmod p
\end{aligned}
$$
那么就有：
$$
f_{x,j-1}-sum_x \equiv f_{y,j-1}-sum_y \pmod p
$$
进一步的：
$$
f_{x,j-1}-f_{y,j-1} \equiv sum_x-sum_y \pmod p
$$
不妨设$f_{y,j-1}<f_{x,j-1}$，那么显然$f_{x,j-1}-f_{y,j-i}=k\times p + sum_x-sum_y$，所以这时选择$y$一定是最优的。

于是我们只需要一边算，一边统计对于所有的$j$，那个位置最优就可以了（下面的代码就对应这种方法）

思路2

还有一种更加离谱的思路，这种思路主要是针对$n\ge p\cdot k$的。

可以发现此时的答案只能是$sum_n$或者是$sum_n+p$因为必须有一个$x$满足$sum_y=x$的$y$超过$k$个。

然后发现答案为$sum_n$当且仅当$sum$的以$n$为结尾的最长不下降子序列$\ge k$，所以直接求最长不下降子序列即可。

Code

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 5e5 + 5, M = 105;
int n, k, p;
int a[N];
int f[2][M];
PII g[M];
int main()
{
    read(n, k, p);
    for(int i = 1;i <= n;i ++) read(a[i]), a[i] = (a[i] + a[i - 1]) % p;
    for(int i = 1, last;i <= n;i ++)
    {
        last = i & 1;
        for(int j = 1;j <= min(i, k);j ++) f[last][j] = g[j - 1].first + (a[i] - a[g[j - 1].second] + p) % p;
        for(int j = 1;j <= min(i, k);j ++)
            if(g[j].first > f[last][j] || i == j) g[j].first = f[last][j], g[j].second = i; 
    }
    write(f[n & 1][k]);
    return 0;
}