公式解説 の母関数

\[ g(x) = \sum_{d=1}^{N-1} 2(N-d) C_{d-1} x^d (1+x)^{2N-2d} \eqqcolon \sum_{d=1}^{N-1} c_d x^d (1+x)^{2N-2d} \]

を \(O(N \log N)\) で求める方法を述べます．\(g(x-1)\) を変形すると，

\[ g(x-1) = \sum_{d=1}^{N-1} c_d (x-1)^d x^{2N-2d} = x^{2N} \sum_{d=1}^{N-1} c_d (x^{-1}-x^{-2})^d = x^{2N} \sum_{d=1}^{N-1} (-1)^d c_d ((x^{-1}-1/2)^2-1/4)^d \]

となります．ここで

\[ h(x) = \sum_{d=1}^{N-1} (-1)^d c_d x^d \]

と定義すれば， \(g(x-1) = x^{2N} h((x^{-1}-1/2)^2-1/4)\) は polynomial Taylor shift，添字の2倍，reverse により計算できます．具体的には，

• \(h\) を計算
• \(-1/2\) の Taylor shift \((= h(x-1/2))\)
• 添字の \(2\) 倍 \((= h((x-1/2)^2))\)
• \(-1/4\) の Taylor shift \((=h((x-1/2)^2-1/4))\)
• reverse \((=x^{2N}h((x^{-1}-1/2)^2-1/4))\)

によって \(g(x-1)\) を求めることができます．最後に，\(g(x-1)\) に対して \(+1\) の Taylor shift を行うことで \(g\) を求めることができます．Taylor shift は \(O(N\log N)\) 時間でできるので，全体の時間計算量は \(O(N \log N)\) です．