CodeForces 466C - Number of Ways

出来なかったので。

問題設定

整数列Aが与えられる。Aを3つのセグメントに分けた時、すべてのセグメントの和が同じになるような分け方は何通りあるか？
ただし、1つのセグメントは必ず1つ以上の要素を含む。

解法

まず、数列Aの総和が3の倍数でなければ、3つのセグメントの和は同じにならない。これは自明。
すると、各セグメントの分け方が条件を満たす時、必ず3つのセグメントの和は必ずになる(S = 数列Aの総和)。

これを念頭に置いた上で、1番目のセグメントをどこまでにするか考えることにする。
ここで1番目のセグメント = 3番目のセグメント = となっているなら、必ず2番目のセグメントもとなる。
故に、0からiまでを1番目のセグメントとして見ていった際の総和がとなった時、jからnまでの総和がとなるjを数えれば良いことがわかる。

これを数えるのは典型で

1. 後ろから累積和を取ってとなる箇所を数えてcnt[j]に保存しておき、
2. 0からi番目の要素までを1番目のセグメントとした際にその総和がとなれば、cnt[i+2]をansに足す(i+2の理由は、 のため)

ことで達成できる（雑な説明）

まあこの典型知らなかったんですけどね！覚えた。