ABC207 E Mod i
$ dp_{i, j} := $ i番目の要素までの部分列について, $ j個に分割する場合の数 としてDPをしていく. まず, このDPをしたときの問題の答えは$ \sum_{k = 1}^N dp_{N, k}となることはすぐにわかるので, 遷移を考えていく. $ B_i = \sum_{i = 1}^i A_iとおく. 単純な遷移は$ dp_{i, j} = \sum_{k | (k < i) \land (B_i - B_k \equiv 0 \mod j)} dp_{k, j - 1}となるが, これでは$ O(N)かかってしまい間に合わない. そこで, 合同式に関する条件の言い換えを行いこの式を$ dp_{i, j} = \sum_{k | (k < i) \land (B_i \equiv B_k \mod j)} dp_{k, j - 1}のように変形する. ここで, $ mem_{i, j} := これまですでに計算し終わったDPテーブルについて, $ \sum_{A_k \equiv j \mod (i + 1)} dp_{j, k}の値 と定義すると, これをDPの値の更新とともに更新していくことで, $ dp_{i + 1, j} = mem_{j - 1, B_i \mod j}と$ O(1)で遷移することができる.
よってこの問題を$ O(N^2)で解くことができた.