优化部分的说明完全一样，只是一个没用 $\LaTeX$, 一个用了。

考虑一段的价值为(pre[i]-pre[j])%p，其中pre为A的前缀和，i为该段结尾，j为上一段结尾。所以发现价值只与pre[j]%p有关系，所以可以在dp时记录f[i][j]表示，当前分成了i段，且转移位置x的pre[x]%p=j的最大值，这样转移就变成O(p)的了。时间复杂度O(nkp)，即可通过本题。