显然有 \(n^3\) 的 dp。
设 \(f_{i,j}\) 表示前 \(i\) 个数里划分 \(j\) 段（\(i\) 为第 \(j\) 段结尾）的方案数，\(s_i=\sum_{i=1}^ia_i\)，则有：
\[f_{i,1}=1,f_{i,j}=\sum_{k=1}^{i-1}[s_i-s_k\equiv 0 \pmod j]f_{k,j-1} \]考虑进一步优化。
我们发现上式可以化为：
\[f_{i,1}=1,f_{i,j}=\sum_{k=1}^{i-1}[s_i\equiv s_k \pmod j]f_{k,j-1} \]优化转移，令 \(g_{i,j}=\sum_{s_k\equiv j\pmod i}f_{k,i-1}\)。
则有
\[f_{i,1}=1,f_{i,j}=g_{j,s_i\bmod j} \] 标签：pmod,规划,sum,动态,优化,bmod,equiv From： https://www.cnblogs.com/WhisperingWillow/p/18195817