ABC169 F - Knapsack for All Subsets

問題：https://atcoder.jp/contests/abc169/tasks/abc169_f

解答：https://atcoder.jp/contests/abc169/submissions/14125789

解法： こちらを参考にしました。 sen-comp.hatenablog.com

Ax1 + Ax2 + ... + Axk = Sとなる(x1, x2, ..., xk)なる組み合わせが見つかった場合、この組み合わせが全体に与える寄与を考えると、(x1, x2, ...,xk)を含むTが全体の和を増加させるが、このTの候補としては残りのxを集合に追加するかしないかの選択肢がある。つまり2^n-k分増えることになる。

dp[i][j] ： i番目まで見ていて、x1 + x2 + ... + xk = j を条件式としたときのfj(T)の値としたDPを考える。
例えば、dp[0][0] = 1 とし、dp[i+1][j+a[i]] += dp[i][j]のように遷移させると、x1+x2+...+xk = jとなる組み合わせの個数は分かるが、fj(T)の値は分からない。fj(T)の値はx1 + x2 + ... + xk = j となるときのkの値が必要となる。

これを解決するアイデアとして、dp[0][0] = 2ⁿとしdp[i+1][j+a[i]] += dp[i][j] / 2とすればよい。1つxiが採用されるたびに、残りの集合の候補が半分になることに対応する。