次は \(O(S\log S)\) 時間でできます．

• \(\sum A_i=S\) を満たす正整数列 \((A_i)\) が与えられる．
• \(F(x)=\prod_i(1+x^{A_i}+x^{2A_i})\) を求めよ．

\(1+x^a+x^{2a}=(1-x^{3a})(1-x^a)^{-1}\) より，

\[\log(1+x^a+x^{2a})=\log(1-x^{3a})-\log(1-x^a)\]

であることを利用します．同じ \(a\) に対する加算をまとめれば，\(\log F\) の計算が調和級数 \(O(S\log S)\) 時間になります．