设 $f_{i,j}$ 表示前 $i$ 个元素分成 $j$ 端的方案数，$s_i = \sum_{j=1}^i a_j$先枚举 $j$，然后 $f_{i,j} = \sum_{k=1}^{i - 1} [a_k\equiv a_i \pmod j] f_{k,j-1}$，对于 $0\leq x < j$ 维护桶 $t_x=\sum_{k} [a_k\equiv x \pmod j] f_{k,j - 1}$ 即可，时间复杂度 $O(n^2 )$。
by __ycx2010__ @ 2024-04-26 18:18:38