CODE THANKS FESTIVAL 2018(Parallel):E-Union(400)

問題

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] := 数 ij 個余るような場合の数

とする。この時 i-12 \times j 個余っていれば ij 個余るようにすることができる。また ia_{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] も解になる。

Submission #3713593 - CODE THANKS FESTIVAL 2018(Parallel)

どこに着目して考察するべきだったか

まず求められているのは、操作前の整数の書き方の場合の数であることを確認しなければならない。

考察は数 i の余りの個数は 数 i-1 の余りの個数に依存することに気づくことができるとDPが見えてくる。

何がバグっていたか

得た知見

類題