beet's soil

競プロのことなど

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

FPS!(素振り)
これ

無限級数の性質から
 \displaystyle \sum_{j=0}^{\infty} x^{a_i j} = \frac{1}{1-x^{a_i}}

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

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

 \log(1-x^{a_i}) = \displaystyle \int \frac{a_i x^{a_i-1}}{1-x^{a_i}} dx
  = \displaystyle \int \sum_{j=0}^{\infty} {a_i x^{(j+1)a_i-1}} dx
  = \displaystyle \sum_{j=1}^{\infty} \int {a_i x^{j a_i-1}} dx
  = \displaystyle \sum_{j=1}^{\infty} {\frac{a_i}{j a_i-1+1} x^{j a_i-1 + 1}} dx
  = \displaystyle \sum_{j=1}^{\infty} \frac{x^{j a_i}}{j}

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

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