手法

${\displaystyle \prod_i(1 \pm x^{d_i}) = \exp\left(\sum_i\log(1 \pm x^{d_i})\right)}$

• $\sum_i\log(1 + x^{d_i})$ の計算
• $\sum_i\log(1 - x^{d_i})$ の計算

$\exp$ の中身が $\Theta(N\log N)$ 時間で計算できるため、全体でも $\Theta(N\log N)$ 時間で計算できる。

逆数

総積を計算してから inverse しても良いが、$\exp$ の中身に $-1$ を掛ければ inverse が不要になる。

$\prod(a_i \pm b_ix^{d_i}) \pmod{x^{N + 1}}$

$d$ が distinct なら $\Theta(N\log N)$ で可能。

$a_i \pm b_ix^{d_i} = a_i(1 \pm \frac{b_i}{a_i}x^{d_i}) = a_i(1 \pm c_ix^{d_i})$ と変換しておく。

${\displaystyle \prod_i(a_i \pm b_ix^{d_i}) = \left(\prod_i a_i \right)\prod_i(1 \pm c_ix^{d_i}) = \left(\prod_i a_i\right) \exp\left(\sum_i\log(1 \pm c_ix^{d_i})\right)}$

• $\sum_i\log(1 + c_ix^{d_i})$ の計算
• $\sum_i\log(1 - c_ix^{d_i})$ の計算

$d$ が distinct でない場合

$\displaystyle \sum_i c_i^k$ が各 $k$ について高速に求まれば良いが、これは yukicoder No. 1145 Sums of Powers なので、$\Theta(N\log^2N)$ 時間で解ける。