答えを \(O(N\log N)\) 時間で求めます。まずは公式解説を参照してください。

公式解説の \(d_2,d_3,\ldots,d_N\) が求まれば良いです。

\(d_0=d_1=0\) とします。また、\(\displaystyle f(x)=\sum_{k=0}^\infty d_k x^k,\ g(x)=\sum_{k=0}^\infty (k+1)!x^k\) とします。

\(\displaystyle n!=\sum_{k=2}^n d_k(n-k+1)!\) \((n\geq 2)\) より、\(\displaystyle \sum_{n=2}^\infty n!x^n=\sum_{n=0}^\infty\sum_{k=0}^n d_k(n-k+1)!x^n\) となります。これは \(f,g\) を用いて \(xg(x)-x=f(x)g(x)\) となります。

したがって \(\displaystyle f(x)=x-\frac x{g(x)}\) となり、\(\displaystyle d_n=[x^n]f(x)=-[x^{n-1}]\frac1 {g(x)}\) となります。\(\displaystyle \frac1 {g(x)}\) はニュートン法を用いることで \(O(N\log N)\) 時間で計算できるため、全体で \(O(N\log N)\) 時間で答えを求めることができます。