問題

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e

制約

$1 \le T \le 300$
$0 \le a_i \le 300$

考え方

DPをする。

$dp[i][j]$ := 数 $i$ を $j$ 個余るような場合の数

とする。この時 $i-1$ が $2 \times j$ 個余っていれば $i$ に $j$ 個余るようにすることができる。また $i$ が $a_{i}$ 個もともと与えられていたとすると、それを加味して余りを構成することができる。

よって以下のようなDPの遷移を考えることができる。

$dp[i][j + k] += dp[i-1][2*j] (0 \le k \le a_{i})$

また、答えになる場合の数は余っている個数が $1$ である場合の数であるから、 $\displaystyle \sum_{i=1}^{T} dp[i][1]$ が答えになる。ただし一番最後は $2$ のべき乗個残っていれば、余っている数が $1$ になるようにすることができるので $\displaystyle \sum_{i=1} dp[T][2^i]$ も解になる。