$x$枚目まで見たときに総和が$y$以上になるようなカードの集合の総数を$dp[x][y]$とすると、漸化式は
$$ \operatorname{dp}[x][y] = \operatorname{dp}[x-1][y] + \operatorname{dp}[x-1][y-a_{x}] $$となる。ここで、$N$番目のカードと$i$番目のカードを入れ替えて同じDPをしたものを$\operatorname{dp}_i$とする。$\operatorname{dp}_i$についても同じ漸化式が成立し
$$ \operatorname{dp}_i[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i] $$順番を入れ替えても$N$枚処理すれば同じ結果になるはずだから$\operatorname{dp}[N][y] = \operatorname{dp}_i[N][y]$が成り立つ。したがって
$$ \operatorname{dp}[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i] $$整理して
$$ \operatorname{dp}_i[N-1][y] = \operatorname{dp}[N][y] - \operatorname{dp}_i[N-1][y-a_i] $$という漸化式が立つ。$i$番目のカードを除いたとき和が$y$以上になるような集合の総数を$f[i][y]$とすると$f[i][y] = \operatorname{dp}_i[N-1][y]$だから
$$ f[i][y] = \operatorname{dp}[N][y] - f[i][y-a_i] $$$\operatorname{dp}$を求めた後、さらに$f$についてDPできる。
カード$i$が不必要
$\Leftrightarrow$ カード$i$を含む和が$K$以上になるような集合と、カード$i$を含まない和が$K$以上になるような集合が一対一対応する
$\Leftrightarrow f[i][K] = \operatorname{dp}[N][K] - f[i][K]$
だから、この等式が成立するような$i$を数えればよい。
$\operatorname{dp}$の値は64ビットに収まらないので、適当にmodをとって扱う。弱衝突耐性があれば十分なので32ビットでよさそう。だめなら複数modを組み合わせればよい。
戻すDPを覚えるために復習。
