ABC169 - F - Knapsack for All Subsets
ABC実質初全完を祝って解説記事。
概要
長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。
f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とする。A[t_1]+A[t_2]+...+A[t_i]==Sになるような部分集合の数。
Tは通りあるが、すべてのTについてのf(T)の合計を求めよ。ただし、大きくなることがあるので
で割ったあまりを答えよ。
制約： 1 <= N, S <= 3000, 1 <= A[i] <= 3000
ACするまで
1. 制約はO(NS)を想定している。普通のナップサックでちょうど間に合う。
2. ある部分集合でSを作れるのならば、そのサイズがkならば、トータルで2^(N-k)回数えられたことになる。->サイズをどうにかして持ちたい！
3. サイズを普通に持たせてDPすると、O(N^2*S)になってTLEする。
4. サイズの代わりに、ナップサックの漸化式で持たせられる値でなんとかならないか？を考える。
5. 最初に2^N通りとして、1つの要素を追加で持たせたときに/2すれば、ナップサックでできる！->AC!
考察
ひとまず、ある集合Pを添え字に持つ要素の和がSになるとき、それは答えにどれぐらい寄与するのだろうか？
すべての部分集合の部分集合を数え上げるので、実質「Pを部分集合に持つ集合の個数」だけ数えられることになる。
つまり、だけ寄与することになる。
というわけで、「dp[i][j] := i個目まで見て、和がjの時の場合の数」のナップサック問題の亜種に個数を持たせて、次のDPテーブルが思いつく。
dp[i][j][k] := i個目まで見て、和がjの時に、k個の要素をすでに持った時の数
しかし、この遷移式はO(N^2*S)の計算量になるので、TLEしてしまう。遷移式にも工夫のやりようがない。
DPテーブルで落とせなさそうな次元を考えてみる。「i個目まで見て」と「和がj」の2つは、どうしても外せないとわかる。となると、なんとかして「k個の要素をすでに持っている」を外すしかない。つまり、普通のナップサックのような遷移式で、いい感じに値を定めて伝播させるしかない。
ここで、答えに寄与する分はだったが、|P|は数を1つ採用するたびに、 *何を採用したのにかかわらず* 、1だけ増える。(寄与する分は、そのたびに半分になる)
つまり、細部を無視して一般化できる、というパターンである。
ならば、最初にdp[0][0] = 2^Nとして、1つ採用するごとに/2していけば、普通のナップサックの遷移式で値を伝播させることができる！
素数MODなので、あらかじめ2の逆元を計算すれば、割り算が可能なのでこれはO(NS)でとけた。
ちなみにこの「何を採用したのにかかわらず」の性質で落とせるのは、DEGwerさんの数え上げPDFにも書かれている(ARC059-F)。
一言
実質初の全完なので、うれしくて書いちゃった。
