\(f \in \mathbb{Q}[[x]]\) を\([x^w] f(x) = \text{総重量}~w~\text{の詰め方の総数}\) で定義します。 \([x^w]f(x)\) はまた、袋の中身に着目すると、総重量 \(w-1\) になるように金塊または空でない袋の多重集合を選ぶ方法の総数であるとも解釈できます。 よって以下の等式が成立します。

\[ f(x) = x \left( \prod_{i=1}^{K} \frac{1}{1 - x^{w_i}} \prod_{w=1}^{\infty} \left( \frac{1}{1 - x^w} \right) ^ {[x^w]f(x)} - 1\right) \]

移項して対数を取ると

\[ \ln \left( \frac{f(x)}{x} + 1 \right) = - \sum _ {i = 1} ^ {K} \ln (1 - x ^ {w_i}) - \sum_{w=1}^{\infty} ([x^w]f(x)) \ln(1-x^w) \]

さらに両辺を微分して移項すると

\[ \left( \frac{f(x)}{x} + 1 \right)' = \left(\frac{f(x)}{x}+1\right) \left(- \sum _ {i = 1} ^ {K} \ln (1 - x ^ {w_i}) - \sum_{w=1}^{\infty} ([x^w]f(x)) \ln(1-x^w)\right)' \]

この式に従うと、\(f\) の係数を次数の小さい順に確定させていくことができます。 \([x^w]f(x)\) が \(w \leq T\) まで確定しているなら、両辺を \(\pmod {x^{T-1}}\) で考えれば左辺から \([x^{T+1}]f(x)\) が分かるという具合です。 したがって、後述する truncated relaxed multiplication を行うことで、この問題を時間計算量 \(O(W (\log(W)) ^ 2)\) で解くことができます。

右辺の右側の項は \(\ln\) を展開すると \(W\) 次以下の項が \(O(W \log(W))\) 個しか存在しない (調和級数) ため高速に計算できることに注意してください。

truncated relaxed multiplication [1]

未知の\(N\) 次多項式 \(f, g\) があり、\(h(x) = f(x)g(x)\) とする。 \(i = 0, 1, \dots, N\) の順に以下のクエリを処理する

• \([x^i]f(x), [x^i]g(x)\) が与えられるので、\([x^i]h(x)\) を出力する

次数 \(M\) の多項式の積を時間計算量 \(O(M \log(M))\) で計算できるとき、truncated relaxed multiplication は時間計算量 \(O(M (\log(M)) ^ 2)\) で処理できる事が知られています。

[1] van der Hoeven, J. (2007). New algorithms for relaxed multiplication. Journal of Symbolic Computation, 42(8), 792-802.