問題概要
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられる。
$Q \ $回にわたって与えられる整数$ \ x_i \ $について、$A \ $の中から以下の条件を満たすようにいくつか選びその総和を$ \ x_i \ $にすることができるか判定せよ。
- $0 \ $個以上$ \ N \ $個以下の整数を選ぶ
- 同じ値の要素を同時に選んではいけない
制約
- $1 \leq N \leq 10^6$
- $1 \leq Q \leq 10^5$
- $-10 \leq a_i \leq 10$
- $-10^9 \leq x_i \leq 10^9$
解説
同じ値のものを一度に選んではいけないという条件がありますが、$a_i \ $は最大でも$ \ 21 \ $種類しかありません。 よって、予め作ることのできる値をbit全探索などにより全列挙することができます。
また、$dp[i][j] \ $を「$ \ i \ $種類目までを選んだ時、値$ \ j \ $を作ることができるか」というbool値を格納するものとした、動的計画法でも答えを求めることができます。
