ABC321 F - #(subset sum = K) with Add and Erase があの遷移でいい理由を理解する

ここでは多項式の実装等は扱わず、どうして遷移があのようになるかを取り扱います。また、わかりやすさのために厳密性を欠く記述があります。

dp 配列と多項式を関連付けると嬉しい場合があります、これもそのうちの一つです。

最初からこの問題を考えると難しいので、箱から取り出すことがない場合を考えましょう。

すると、これは以下のように dp 配列を更新することで解けるはずです。

$\displaystyle dp[i] \leftarrow dp[i-x]+dp[i]$

ここで、これを多項式によって書くことを考えます。

仮に、多項式の次数を $i$ に相当するもの、 $y^i$ の係数を $dp[i]$ の中身に相当するものとし、これをどう遷移させるかを考えます。

(具体的には $dp[0]+dp[1]y+dp[2]y^2+\cdots +dp[K]y^k$ という多項式です)

ここで考えていた dp は

$\displaystyle (今の状態) \leftarrow (一つ前の状態) + (一つ前の状態の和に x だけ下駄をはかせたもの)$

と書き直すことができます。

一つ前の状態の和に $x$ だけ下駄をはかせたものというのは、一つ前の状態に $y^x$ を掛けたものに等しいです。

よって、次のように書けることがわかります。

$\displaystyle (今の状態) \leftarrow (一つ前の状態) \times (1+y^x)$

この形のまま、箱から取り出すことがある場合を考えましょう。

問題文から、取り出される際に $(今の状態)$ が $(1+y^x)$ を因数に持つことがわかります。

ここで多項式は乗法について可換ですから、 $(今の状態)$ の一番右に $(1+y^x)$ をもってきて、 $(1+y^x)$ で割って打ち消してしまいましょう。

直感的に乗算と除算は逆の演算ですから、dp として扱う際も逆の操作をすればよさそうです。

したがって、取り出すときの更新は以下のように書けます

$\displaystyle dp[i] \leftarrow dp[i] - dp[i-x]$

よって、この遷移を実装して、 $O(QK)$ 時間でこの問題を解くことが出来ました。