概要
感謝の続きです
ABC159 F - Knapsack for All Segment
どういうDPを書いたらいいのかわからん...
概要
$A_1$, $A_2$, $\ldots$, $A_N$ に含まれる全ての区間について考える。
それぞれの区間$[L_i, R_i]$について、
$$A_{x_1} + A_{x_2} + ... + A_{x_k} = S$$
を満たす$L_i \leq x_1 \leq x_2 \leq ...\leq x_k \leq R_i $な$x_i$の組みの数を数えて、その和を求めよ。
立式
(難しいので後で書く)
提出
この計算が難しい。これは覚えておきたい。
ABC169 F - Knapsack for All Subsets
どういうDPを書いたらいいのかわからん...
概要
$A_1$, $A_2$, $\ldots$, $A_N$ の全ての部分集合$2^N -1$通りについて考える。
それぞれの部分集合について、
$$A_{x_1} + A_{x_2} + ... + A_{x_k} = S$$
を満たす$x_1, x_2, ..., x_k$の組の数を数えて、その和を求めよ。
立式
$f_i = (1 + T^{A_i})$として、$f_i$について考えるかどうか、$2^N$通りある、ですね。
$$ F = (1+f_1)(1+f_2)...(1+f_N) = (2 + T^{A_1})(2 + T^{A_2})...(2+T^{A_N}) $$
の、$T^{S}$の係数が答え。
提出
書いてみると簡単。
ABC171 F - Strivore
コンテストで見た時は手も足も出なかった...
概要、立式
maspyさんの素晴らしい解説があるので省略。
$-K$乗の形はよく出てきます。↓で効率的に計算できます。すごい。
提出
F問題が7行くらいで解けました。嬉しい。
まとめ
解けたら追記していく