A: Biscuits - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

数列A[i]が与えられるので、部分列をとってその和の余りを0または1にしたい。そのような部分列は何通りあるか？

k番目までの数列の部分列をとったときにあまりが0または1になる組み合わせをa[0][k], a[1][k]とおく。A[k + 1]が奇数または偶数によって場合分けし、dpを更新していく。O(N)。