\prod (1+x^a_i+x^2a_i+...) の先頭n項をO(n log n)で

FPS！（素振り）
これ

無限級数の性質から
∑j=0∞xaij=11−xai${\displaystyle \sum _{j=0}^{\mathrm{\infty }}{x}^{a_{i}j}=\frac{1}{1-x^{a_i}}}$

logをとる
log(11−xai)=−log(1−xai)${\displaystyle \log \left(\frac{1}{1-x^{a_i}}\right)=-\log (1-x^{a_i})}$

logの定義にしたがって計算する
ref.

log(1−xai)=∫aixai−11−xaidx$\log (1-x^{a_i})={\displaystyle \int \frac{a_i{x}^{a_i-1}}{1-x^{a_i}}dx}$
=∫∑j=0∞aix(j+1)ai−1dx$={\displaystyle \int \sum _{j=0}^{\mathrm{\infty }}{a}_i{x}^{(j+1)a_i-1}dx}$
=∑j=1∞∫aixjai−1dx$={\displaystyle \sum _{j=1}^{\mathrm{\infty }}\int a_i{x}^{j{a}_i-1}dx}$
=∑j=1∞aijai−1+1xjai−1+1dx$={\displaystyle \sum _{j=1}^{\mathrm{\infty }}\frac{a_i}{j{a}_i-1+1}{x}^{j{a}_i-1+1}dx}$
=∑j=1∞xjaij$={\displaystyle \sum _{j=1}^{\mathrm{\infty }}\frac{x^{j{a}_i}}{j}}$

これらの和の先頭n項は ai≤n$a_i\le n$ なる ai$a_i$ をその値毎にまとめて計算すると調和級数から O(nlogn)$O(n\log n)$ で計算できる

指数法則から、求めるものは和をexpしたものになる
expの計算量も O(nlogn)$O(n\log n)$

例

atcoder.jp