この解説では自然言語を基調とし、それによって導かれる計算量 \(O(W \log W)\) の方法を紹介します。

便宜上、次のような表記を用います。

• 数列 \(X\) の \(i\) 番目の要素を \(X[i]\) と表します。
• 数列 \((X[l],X[l+1],\ldots ,X[r-1])\) を \(X[l\ldots r]\) と表します。
• 数列 \(X,Y\) の畳み込み \(Z[i]=\sum_{j+k=i}X[j]Y[k]\) を \(Z=X*Y\) のように表します。

この解説で用いる計算（ Multiset Sum と呼ぶことにします。）

\(\#_p\) Subset Sum (https://judge.yosupo.jp/problem/sharp_p_subset_sum) を逆数で行って多重集合に対応する、と聞いて分かれば読まなくてよいです。

数列 \(A\) が与えられる。これは重さ \(w\) の品物が \(A[w]\) 種類、無尽蔵にあることを表す。重さの和が \(W\) になるような品物の選び方を \(B[W]\) としたとき、数列 \(B[0 \ldots W_{\text{max}}+1]\) を求めよ。

形式的べき級数を用いると \(\prod_i (\frac{1}{1-x^i})^{A[i]}\) のように表せますが、逆数の対数にあたる \(\sum_i A[i]\log(1-x^i)\) は係数を愚直に加算すると求まります。よって、上の問題を高速( \(O(W_{\text{max}} \log W_{\text{max}})\) 時間)で解くことができます。

解説

まず、ある袋の直下にある金塊がちょうど \(1\) 個であるような問題に帰着します。金塊の情報は次の値で表され、 Multiset Sum で求まります。

• \(C_{\text{gold}}[w]:=\) （金塊の多重集合（空を許す）で、重さの合計が \(w\) であるようなものの個数）

すると、袋に直下の金塊を吸収させることで重袋のみの問題にできます。

• \(C_{\text{bag}}[w]:=C_{\text{gold}}[w-1]=\) （重袋であって、重さが \(w\) であるようなものの個数）

ただし、空かつ重さ \(1\) の重袋は許されないことに注意します。 \(\cdots[1]\)

\([1]\) に注意しつつ重袋を入れ子にしたものを多様袋とします。求めるものは重さ \(w\) の多様袋の個数です。

• \(Q[w]:=\) （多様袋であって、重さが \(w\) であるものの個数）

\(Q[0\ldots 2]=(0,0)\) から始めて、この数列の長さを倍々にします。倍にする前の長さを \(n\) とします。

数え上げの数列の長さを倍々にするときにはよく考えることですが、ある多様袋の内部について重さ \(n\) 以上の極小な多様袋に注目します。

• \(Q_{\text{pre}}[w]:=\) （重さ \(n\) 以上の多様袋を内部に含まない、重さ \(w\) の多様袋の個数） \((n \leq w \lt 2n)\)

これは、いくつかの重さ \(n\) 未満の多様袋を \(1\) つの重袋に入れて作られるので、 \(Q_{\text{pre}}[n\ldots 2n]=(\text{Multiset Sum}(Q)*C_{\text{bag}})[n\ldots 2n]\) として求まります。（ここで \([1]\) の違反を防ぐために、 \(n=2\) から始めなければなりません。）

重さ \(n\) 以下の極小な多様袋は一意なので、この多様袋を他の多様袋や重袋でラッピングしたものが \(Q\) で数え上げるものです。よって、次の数え上げを考えます。

• \(C_{\text{wrap}}[d]:=\) （特別な多様袋をラッピングして重さを \(d\) だけ増加させる方法の個数）

すると \(Q[n\ldots 2n]=(Q_{\text{pre}}[n\ldots 2n]*C_{\text{wrap}})[0\ldots n]\) より、 \(Q\) の長さを倍にできました。

\(n=2\) のとき、 \(C_{\text{wrap}}[0 \ldots 2]=(1,1)\) です。次はこの数列の長さを倍にしますが、他の多様袋と一緒に包んで重さ \(n\) 以上になったらラッピングするだけなので、 \(Q\) に対する操作と（全くではないが）同じことです。

\(Q[0 \ldots W+1]\) が求まるまで上記を行い、 \(Q[2 \ldots W+1]\) を出力します。

全体の計算量は \(O(W \log W)\) です。

解答例 (C++, atcoder::convolution 使用)