最初の考察として、以下の条件が導かれます。

カード \(i\) が必要 \(\Leftrightarrow\) \(i\) を含まないカードの集合であって、総和が \(\lbrack K - a _ i, K )\) に入るものが存在する

各 \(1 \leq i \leq N\) と \(0 \leq j \lt K\) について「\(i\) を含まないカードの集合で総和が \(j\) になるものが存在するかどうか」を計算することが目標です。 この条件を多項式で表現すると

\[\begin{aligned} \lbrack x ^ j \rbrack \prod _ {k \neq i} (1 + x ^ {a _ k}) \neq 0 \end{aligned}\]

となります。 これを各 \(i\) について計算することは、\(F := \prod _ {k} (1 + x ^ {a _ k})\) を計算した後、\(F / (1 + x ^ {a _ i})\) を計算することで効率的に行えます。 これらの計算は全て \(\pmod {x ^ K}\) で行えることに注意すると、時間計算量は \(\Theta(NK)\) となります。 ただし、係数がとてつもなく大きくなることを無視しています。

係数が大きくなるという問題点を解消するために、\(P\) を素数として、係数を \(\pmod P\) で計算することを考えます。 係数が \(2 ^ N\) 以下であることを考えると持ちうる素因数の個数はさほど大きくならないため、\(P\) をランダムに選択することで、十分に高い確率で \(\pmod P\) でも非零になることを検出できます。

少し工夫することで、\(P\) を固定することも可能です。 以降、係数は全て \(\pmod P\) で考えることとします。 各 \(i\) について変数 \(r _ i\) を導入し、今までの議論の \(1 + x ^ {a _ k}\) を \(1 + r _ k x ^ {a _ k}\) に置き換えます。 例えば前述した \(i, j\) についての条件は \(\lbrack x ^ j \rbrack \prod _ {k \neq i} (1 + r _ k x ^ {a _ k})\) が (\(r\) についての多項式として) \(0\) でないことと同値です。 実際この多項式は

\[\begin{aligned} \sum \left\lbrace \prod _ {k \in T} r _ k : T \subseteq S - i, \sum _ {k \in T} a _ k = j \right\rbrace \end{aligned}\]

と等しく、\(\pmod P\) をとることで \(0\) になってしまうということはありません。 \(0\) でない多項式の変数にランダムな値を代入した際に \(0\) になる確率を上から抑える定理として Schwartz–Zippel lemma が知られており、各 \(r _ i\) に \(\lbrack 0, P)\) の整数を一様ランダムに代入して全ての計算を行うアルゴリズムが正当化されます。 \(P\) がワードサイズに収まるとして、時間計算量は \(\Theta(NK)\)、誤答の確率は \(\mathrm{O}(N ^ 2 / P)\) です。

実装例 https://atcoder.jp/contests/abc056/submissions/23470864