DP難しい。
全事象は塔を建てるか建てないかの2通りの組み合わせで、通り。このうち題意をみたす塔の立て方のパターン数の確率を求めれば良い。
良い塔の建て方は、奇数の和でNになる場合の数なので、これをDPで求めたい。
気づき
- 累積和＋DPは貰うDPのほうが見えやすい
最初配るDPで考えていて、累積和で計算量を落とせることに気づかなかった。
貰うDPで考えて、あるインデックスkのときにどこから遷移してくるかを考えると、
k-1,k-3,k-5,...1または0（偶奇で変わる）
となる。
遷移として書くと、
dp[i] = dp[i-1] + dpi[i-3]+ dp[i-5] + ... dp[0]またはdp[1]
これはdp更新時に累積和も同時に更新していけば計算量を落とすことができる。
2個おきに和をとると、更新するインデックスが偶数と奇数のときでずれるので、実装上は偶数インデックスの累積和と奇数インデックスの累積和を別に用意したほうが混乱が少ない。
