らての精進日記

修行をします

codechef:PSUM

問題を解く過程で考えたことを書くよ

題意

Contest Page | CodeChef


N個の宝がある
i番目の宝の重さはciで、価値はviである
重さSまで許容するナップザックがある

ナップザックに収まるような(重さの合計がSを越えないように)宝の選び方すべてについて、(価値の合計)^Kを計算して、その総和を求めてください mod 998244353

N,S<=100
K<=100
ci<=100
vi<=10^9

考え方

前からdpしていくイメージで考える

今、[1,i-1]の中からいくつか選んで、その価値の総和がvであるとする。そして、v^Kが求まっているとする

このとき、(v+vi)^Kを計算できると嬉しい(i番目の宝を追加したときの価値^K)
二項展開すると、(v+vi)^K=Σbinom(K,k)v^k vi^(K-k)
あ、exponential generating functionの積が計算できればいいじゃん
→modが998244353 勝ちました


負けました
www.codechef.com


上記の解法について詳しく書くと、
dp[i][j][k]:=宝を[1,i]から選んで、重さの総和がjとなるようなすべての選び方についての、価値^kの総和
と定義すると、二項展開の式から、
dp[i][j][k]=dp[i-1][j][k]+ Σ[l=0,...,k] binom(k,l)dp[i-1][j-ci][l]*vi^(k-l)
という漸化式が生えて、これはO(NSK^2)で計算できる
ここで、漸化式をよく見るとexponential generating functionの積を計算するような形になっている gg




上記をさらに詳しく説明すると、
2つの数列{ai},{bj}があったときに、新たな数列
{ck} (ck=Σ[l=0,...,k] binom(k,l) ai*b
数式を普通に打ち込んだら読みにくいだろ やめました