ABC 137 F - Polynomial Construction

• 問題
• AC

$g(x) := x(x-1)...(x-p+1)$, $g_i(x) := g(x)/(x-i)$と定める。$a_i=1$である添え字$i$を$i_1, i_2, ..., i_k$とするとき、求める多項式$f$は次のように書ける:

$f(x) := g_{i_1}(x)/g_{i_1}(i_1) + g_{i_2}(x)/g_{i_2}(i_2) + ... + g_{i_k}(x)/g_{i_k}(i_k)$

したがって、$g(x)$を多項式乗算で求めたあと、必要な$i$について$x-i$で割って$g_i(x)$を求めればよい。 乗算は最初はFFTでやったのだが、よく考えると一次式を掛けていくだけなので素朴な掛け算で${\mathcal O}(p)$だった。割り算も同様で、一次式で割るので高速な多項式除算を実現する必要はない。つまり、

$g(x) = \alpha_{p}x^{p}+\alpha_{p-1}x^{p-1} + ... + \alpha_1x + \alpha_0$

$\begin{aligned} g(x) & = (x-i)(\beta_{p-1}x^{p-1}+\beta_{p-2}x^{p-2} + ... + \beta_0) \\ & = \beta_{p-1}x^p+(\beta_{p-2}-i\beta_{p-1})x^{p-1}+...+(\beta_0-i\beta_1)x- \beta_0i \end{aligned}$

の2つの式を比較すると

$\beta_{p-1} = \alpha_p\\ \beta_{p-2} = \alpha_{p-1} + i\beta_{p-1} \\ ... \\ \beta_0 = \alpha_1 + i\beta_1$

となっていて、$\beta_{p-1}$から順次求まることがわかる。計算量は${\mathcal O}(p^2)$。

---

${\mathcal O}(N^2)$の素朴な乗算と組立除法をやっているだけなので、ライブラリとして用意しておいたほうが良さそう。

http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf
一般の多項式除算と互除法について。