ARC 070 D - No Need

• 問題
• AC

$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を覚えるために復習。

参考: https://sen-comp.hatenablog.com/entry/2019/11/06/121325