メモ: Bostan-Mori 法で計算できるものまとめ

$\displaystyle \left \lbrack x ^ k \right \rbrack \frac{P(x)}{Q(x)}$

\begin{align} \frac{P(x)}{Q(x)} &= \frac{P(x) Q(-x)}{Q(x) Q(-x)} \cr &= \frac{E(x ^ 2) + x O(x ^ 2)}{V(x ^ 2)} \end{align}

であるから、

\begin{align} \left \lbrack x ^ k \right \rbrack \frac{P(x)}{Q(x)} &= \begin{cases} \displaystyle \left \lbrack x ^ {k / 2} \right \rbrack \frac{E(x)}{V(x)} & \quad (k = 0 \pmod 2) \cr \displaystyle \left \lbrack x ^ {(k - 1) / 2} \right \rbrack \frac{O(x)}{V(x)} & \quad (k = 1 \pmod 2) \end{cases} \end{align}

base case

$\mathbb{K}( (x) )$

$d := \mathrm{ord}(Q(x) )$ とする。

\begin{align} \left \lbrack x ^ 0 \right \rbrack \frac{P(x)}{Q(x)} &= \frac{\left \lbrack x ^ d \right \rbrack P(x)}{\left \lbrack x ^ d \right \rbrack Q(x)} & & \left( \mathrm{ord}(P(x) ) \geq d \right) \cr \left \lbrack x ^ {-1} \right \rbrack \frac{P(x)}{Q(x)} &= \frac{\left \lbrack x ^ {d - 1} \right \rbrack P(x)}{\left \lbrack x ^ d \right \rbrack Q(x)} & & \left( \mathrm{ord}(P(x) ) \geq d - 1 \right) \end{align}

$\mathbb{K}( (x ^ {-1}) )$

$d := \mathrm{deg}(Q(x) )$ とする。

\begin{align} \left \lbrack x ^ 0 \right \rbrack \frac{P(x)}{Q(x)} &= \frac{\left \lbrack x ^ d \right \rbrack P(x)}{\left \lbrack x ^ d \right \rbrack Q(x)} & & \left( \mathrm{ord}(P(x) ) \leq d \right) \cr \left \lbrack x ^ {-1} \right \rbrack \frac{P(x)}{Q(x)} &= \frac{\left \lbrack x ^ {d - 1} \right \rbrack P(x)}{\left \lbrack x ^ d \right \rbrack Q(x)} & & \left( \mathrm{ord}(P(x) ) \leq d - 1 \right) \end{align}

$\displaystyle \left \lbrack x ^ {( l, r \rbrack} \right \rbrack \frac{1}{F(x)}$

$d \geq \mathrm{deg}(F(x) )$ とする。

\begin{align} \frac{1}{F(x)} &= F(-x) \frac{1}{F(x) F(-x)} \cr &= F(-x) \frac{1}{V(x ^ 2)}
\end{align}

であるから、 $\displaystyle \left \lbrack x ^ {( l, r \rbrack} \right \rbrack \frac{1}{F(x)}$ は $\displaystyle \left \lbrack x ^ {( l - d, r \rbrack} \right \rbrack \frac{1}{V(x ^ 2)}$ から計算できる。さらにこれは $\displaystyle \left \lbrack x ^ {( \lfloor (l - d) / 2 \rfloor, \lfloor r / 2 \rfloor \rbrack} \right \rbrack \frac{1}{V(x)}$ から求まる。

base case

最終的に、求める区間が $\lbrack - d , 0 \rbrack$ に包含されるようになる。

$\mathbb{K}( (x) )$

最初に $\left \lbrack x ^ 0 \right \rbrack F(x) \neq 0$ となるようにしておく。

\begin{align} \left \lbrack x ^ 0 \right \rbrack \frac{1}{F(x)} &= \frac{1}{\left \lbrack x ^ 0 \right \rbrack F(x)} \end{align}

$\mathbb{K}( (x ^ {-1}) )$

最初に $\left \lbrack x ^ d \right \rbrack F(x) \neq 0$ となるようにしておく。

\begin{align} \left \lbrack x ^ {-d} \right \rbrack \frac{1}{F(x)} &= \frac{1}{\left \lbrack x ^ d \right \rbrack F(x)} \end{align}

$x ^ k \pmod {F(x)}$

$d := \mathrm{deg}(F(x) )$ とする。

\begin{align} x ^ k &= Q(x) F(x) + R(x) \end{align}

を満たす $d$ 次未満の多項式 $R(x)$ を求めたい。ただし $Q(x)$ は何らかの多項式である。 $\mathbb{K} ( (x ^ {-1}) )$ において両辺を $F(x)$ で割って

\begin{align} \frac{x ^ k}{F(x)} &= Q(x) + \frac{R(x)}{F(x)} \end{align}

を得る。 $\displaystyle \frac{x ^ k}{F(x)}$ のうち $x$ の指数が負の部分が $\displaystyle \frac{R(x)}{F(x)}$ に対応するから、これを計算して $F(x)$ を掛ければ $R(x)$ が得られる。よって $\displaystyle \left \lbrack x ^ {\lbrack - d , 0 )} \right \rbrack \frac{x ^ k}{F(x)} = \left \lbrack x ^ {\lbrack - k - d , -k )} \right \rbrack \frac{1}{F(x)}$ を求めればよい。

$x ^ {-k} \pmod {F(x)}$

$d := \mathrm{deg}(F(x) ), ~ \left \lbrack x ^ 0 \right \rbrack F(x) \neq 0$ とする。

\begin{align} x ^ k R(x) + Q(x) F(x) &= 1 \end{align}

を満たす $d$ 次未満の多項式 $R(x)$ を求めたい。ただし $Q(x)$ は $k$ 次未満の多項式である。 $\mathbb{K}( (x) )$ において両辺を $x ^ k F(x)$ で割って

\begin{align} \frac{R(x)}{F(x)} + \frac{Q(x)}{x ^ k} &= \frac{1}{x ^ k F(x)} \end{align}

を得る。 $\displaystyle \frac{1}{x ^ k F(x)}$ のうち $x$ の指数が非負の部分が $\frac{R(x)}{F(x)}$ に対応するから、これを計算して $F(x)$ を掛ければ $R(x)$ が得られる。よって $\displaystyle \left \lbrack x ^ {\lbrack 0 , d )} \right \rbrack \frac{1}{x ^ k F(x)} = \left \lbrack x ^ {\lbrack k , k + d )} \right \rbrack \frac{1}{F(x)}$ を求めればよい。