No.332

ナップザック問題ではあるが, 愚直にやると $O(2^N)$ だし, 素直な DP でやると $O(NX)$ だしで間に合わない.

そこで, $A_1 \times A_2 \times \dots \times A_N \leq 10^{100}$ の条件を使う.

この条件から, $A_i \geq 10^5$ となるのは高々20個であることがわかる. そこで, $A_i \lt 10^5$ の要素だけ集めたものを $B$ として, $B$ の要素で作れる数値を DP で計算する. $B$ だけで作れる数値の最大値は $10^7$ であり, ループ回数は $100 \times 10^7$ となるが, DP で行う操作はビットシフトとビットORで可能なので定数倍高速化で間に合わせる.

$A_i \geq 10^5$ の要素だけ集めたものを $C$ として, BitDP で作れる数値を数え上げ, $B$ の要素で作れる数値と足して $X$ になるかどうか突き合わせる.

$X$ が作れたならばあとは経路復元で使う数値を取り出せばいい.

D言語のBitArrayは64の倍数でシフトしたときにバグがあるようで, コードでは無理やり回避している.