FPS24 N - 硬貨 2
$ (1+x+\cdots+x^{A_1})(1+x^2+\cdots+x^{2A_2})\cdots (1+x^N+\cdots+x^{NA_N})[x^N] が答え．
$ \prod_{j=1}^N \frac{1-x^{j(A_j+1)}}{1-x^j}を計算するが，そのまま掛け算すると間に合わない．
exp-logのテクを使う．
code:tex
\begin{align*}
\prod_{j=1}^N \frac{1-x^{j(A_j+1)}}{1-x^j} &= \exp \log \prod_{j=1}^N \frac{1-x^{j(A_j+1)}}{1-x^j}\\
&= \exp \left( \log \prod_{j=1}^N (1-x^{j(A_j+1)}) - \log \prod_{j=1}^N (1-x^j) \right) \\
&= \exp \left( \sum_{j=1}^N \log(1-x^{j(A_j+1)}) - \sum_{j=1}^N \log(1-x^j) \right)
\end{align*}
ここで，$ \log(1-x^k)=-\sum_{j=1}^\infty \frac{1}{j}x^{jk} なので，同じ$ kについてまとめて処理することで$ \sum \log(1-x^{A_i})的なものを調和級数より$ O(N\log N)で求められる．残りの部分も計算可能なので全体として$ O(N\log N).
コメント