公式解説によると、総積 \(P_n = \prod_{i = 1}^n (x + i)\) の計算が計算できればよいのですが、これは次の方法で \(O(N \log N)\) 時間で行うことが出来ます。

\[ P_d(x) = \begin{cases} P_{d/2}(x) \cdot P_{d/2}(x + d/2) & (d = 0 \pmod 2) \\ P_{d - 1}(x) \cdot (1 + dx) & (d = 1 \pmod 2) \end{cases} \]

なお \(P_{d/2}(x + d/2)\) の計算は polynominal Taylor shift の枠組みで \(O(d \log d)\) 時間で行うことが出来ます。