形式的冪級数のライブラリをありがたく使ってAtcoderの問題を解く(つづき)

どういうDPを書いたらいいのかわからん...
atcoder.jp

$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$の組みの数を数えて、その和を求めよ。

あとでかく

この計算が難しい。これは覚えておきたい。
atcoder.jp

どういうDPを書いたらいいのかわからん...
atcoder.jp

$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}$の係数が答え。

書いてみると簡単。
atcoder.jp

コンテストで見た時は手も足も出なかった...
atcoder.jp

maspyさんの素晴らしい解説があるので省略。
maspypy.com

$-K$乗の形はよく出てきます。↓で効率的に計算できます。すごい。

F問題が7行くらいで解けました。嬉しい。
atcoder.jp

300億円欲しい