淺談多項式除法 Part 2: 一些應用

多項式乘法常常在一些計數問題上出現，例如 UVa 12298 或 ICPC 5705。多項式除法雖然比乘法冷門，也是有一些應用的。

問題一：給定 $n-1$ 次複係數多項式 $f(z)$ 和 $n$ 個點 $z_1, \ldots, z_n \in \mathbb{C}$，在 $O(n(\log n)^2)$ 時間內求出 $f(z_1), \ldots, f(z_n)$。

這題出自 CLRS 上的習題。設 $1 \leq l \leq r \leq n$ 並考慮

$$p(z; l, r) := \prod_{k=l}^r(z-z_k) = (z-z_l)\ldots(z-z_r)$$

觀察到 $f(z)$ 在 $z = z_l, \ldots, z_r$ 上的值，和 $f(z)\operatorname{mod}p(z; l, r)$ 在 $z = z_l, \ldots, z_r$ 上的值相同。假定 $p(z; 1, \lfloor n/2\rfloor)$ 和 $p(z; \lfloor n/2\rfloor+1, n)$ 為已知，我們可以分別計算

• $f(z)\operatorname{mod}p(z;1, \lfloor n/2\rfloor)$ 在 $z = z_1, \ldots, z_{\lfloor n/2\rfloor}$ 的值
• $f(z)\operatorname{mod}p(z; \lfloor n/2\rfloor+1, n)$ 在 $z = z_{\lfloor n/2\rfloor+1}, \ldots, z_n$ 的值

這樣的 divide and conquer 時間複雜度是 $T(n) = 2T(n/2) + O(n\log n) = O(n(\log n)^2)$。

那麼要怎麼求出過程中需要的 $p(z; l, r)$ 們呢？回想一下，計算 $p(z; 1, n) = p(z;1, \lfloor n/2\rfloor)p(z; \lfloor n/2\rfloor+1, n)$ 有一個顯然的 D&C 做法，時間複雜度也是 $O(n(\log n)^2)$，且中間過程算到的 $p(z; l, r)$ 們正好就是前一個 D&C 所需要的 $p(z; l, r)$ 們。這樣一來，整體的時間複雜度就是兩次 D&C 的時間複雜度，$O(n(\log n)^2)$。

這題可以在 ZJ c491 測。

問題二：給定 $D_0$ 和 $c_1, \ldots, c_n$。已知 DP 式 $D_i = \sum_{j=1}^i c_jD_{i-j}$，在 $O(n\log n)$ 時間內求出 $D_1, \ldots, D_n$。

其實只要發現了下面這個性質就結束了。考慮 $$f(x) := x^n - \sum_{i=1}^n c_i x^{n-i}$$ 則 $D_0 x^{2n}$ 除以 $f(x)$ 的商式就是 $\sum_{i=0}^n D_i x^{n-i}$，因此計算 $D_1, \ldots, D_n$ 只需要 $O(n\log n)$ 時間。這個性質的證明如下：設 $D_0 x^{2n}$ 除以 $f(x)$ 的商式是 $\sum_{i=0}^n a_i x^{n-i}$，亦即 $$D_0 x^{2n} = (x^n - \sum_{i=1}^n c_i x^{n-i})(\sum_{i=0}^n a_i x^{n-i}) + O(x^{n-1})$$ 比較等式兩邊 $x^{2n}$ 項係數可得 $a_0 = D_0$。另，設$1 \leq k \leq n$，比較 $x^{2n-k}$ 項係數可得 $$a_k - (c_1a_{k-1} + c_2a_{k-2}+ \ldots +c_ka_0) = 0$$ 用數學歸納法可知 $a_k = D_k$。

這題可以在 ZJ c492 測。

問題三：給定 $a_0, a_1, \ldots, a_{k-1}$ 和 $c_1, \ldots, c_k$，並對於所有的 $i \geq k$，遞迴定義 $$\begin{equation}\label{recursion}a_i := \sum_{j=1}^k c_j a_{i-j}\end{equation}$$ 在 $O(k\log k\log n)$ 時間內求出 $a_n$。

這算是相當經典的問題，網路上也有不少時間複雜度 $O(k^3\log n)$ 的 naïve(?) 演算法介紹。和上一題一樣，只要發現下面這個性質就幾乎結束了。考慮 $(\ref{recursion})$ 的特徵多項式

$$f(x) := x^k - \sum_{i=1}^k c_i x^{k-i}$$

令 $x^n$ 除以 $f(x)$ 的餘式為 $r(x) := \sum_{i=0}^{k-1} r_ix^i$，則 

$$\begin{equation}\label{property}a_n = \sum_{i=0}^{k-1}r_ia_i\end{equation}$$

當然我們不是直接計算 $x^n\operatorname{mod}f(x)$，而是用快速冪做 $O(\log n)$ 次的多項式運算，整體時間複雜度 $O(k\log k\log n)$。

那麼 $(\ref{property})$ 怎麼證明呢？其實用數學歸納法也不難證明，只是這樣會讓人有「到底是怎麼想到的OAO」的感覺。以下我採用稍微迂迴的方法，說明 $(\ref{property})$ 本來就會成立。題外話，這個手法其實是線性差分方程的常用手法。

首先我們來重新定義什麼是一個數列。一個數列 $a_0, a_1, a_2, \ldots$ 是一個函數 $a: \mathbb{Z}_{\geq 0} \to \mathbb{C}$，並令所有這種函數的集合為 $S$。接著，我們在 $S$ 上引入加法和係數積如下：

• 設 $a, b \in S$，則 $a+b \in S$ 定義為 $(a+b)(i) := a(i) + b(i)$ 對於所有的 $i \in \mathbb{Z}_{\geq 0}$。
• 設 $a \in S, \alpha \in \mathbb{C}$，則 $\alpha a \in S$ 定義為 $(\alpha a)(i) := \alpha a(i)$ 對於所有的 $i \in \mathbb{Z}_{\geq 0}$。

不難發現在這兩個運算下 $S$ 是個 $\mathbb{C}$-vector space。接著我們引入左移算子 $\mathscr{L}: S \to S$：設 $a \in S$，定義 $(\mathscr{L}a)(i) := a(i+1)$ 對於所有的 $i \in \mathbb{Z}_{\geq 0}$，可以發現 $\mathscr{L}$ 是線性的。這樣一來，$(\ref{recursion})$ 就能寫成 $(f(\mathscr{L}))a = 0$，而我們想算的 $a_n$ 其實就是 $\mathscr{L}^na$ 代入 $0$ 的函數值。將 $\mathscr{L}^n$ 除以 $f(\mathscr{L})$ 得到 $\mathscr{L}^n = q(\mathscr{L})f(\mathscr{L}) + r(\mathscr{L})$，則

$$\mathscr{L}^na = q(\mathscr{L})((f(\mathscr{L}))a) + (r(\mathscr{L}))a = (r(\mathscr{L}))a$$

將 $r(\mathscr{L})$ 寫成 $\sum_{i=0}^{k-1}r_i\mathscr{L}^i$，就有

$$(r(\mathscr{L}))a = \sum_{i=0}^{k-1}r_i(\mathscr{L}^ia)$$

因此

$$a_n = (\mathscr{L}^na)(0) = \sum_{i=0}^{k-1}r_i((\mathscr{L}^ia)(0)) = \sum_{i=0}^{k-1}r_ia_i$$

這恰好就是 $(\ref{property})$。

這題可以在 ZJ c490 測。另外，如果多項式乘法和取餘的部分用 naïve 演算法代替，可以做到 $O(k^2\log n)$ 的時間複雜度，效率依然比 $O(k^3\log n)$ 高。