ABC169-F Knapsack for All Subsets
問題
解法
問題のタイトル通りナップザック問題を考える．
dp[i][j]:i番目までの要素までを用いた部分集合Sを考えたとき，総和がjになるようなSの部分集合の数
とすると，dp[n][s]が答えとなる．
すると，遷移としては以下が考えられる．
（要素a[i]を使う）：a[i]を使うので，当然部分集合Sにもa[i]が入っている必要があり，そして元の総和にはa[i]が足される．よってdp[i+1][j+a[i]]にはdp[i][j]からの遷移が完全に1:1で含まれる．
dp[i+1][j+a[i]]+=dp[i][j]
（要素a[i]を使わない）：a[i]は結局使わないので，部分集合Sに入っていようが入っていまいがどちらでもいい．よってdp[i+1][j]にはdp[i][j]からa[i]を部分集合に含む場合と含まない場合の２パターンの遷移が考えられる．
dp[i+1][j]+=2*dp[i][j]
あとは，上記の式を順に計算していくことによって答えが求まる．
