多項式與生成函數簡介

多項式與生成函數

操縱有限項/無限項的多項式是 OI 數學中，尤其是生成函數中的重要內容。

以快速傅里葉變換為基石的多項式算法賦予了算法競賽選手直接操縱生成函數的能力。

基本概念

對於求和式 \(\sum a_nx^n\)，如果是有限項相加，稱為多項式，記作 \(f(x)=\sum_{n=0}^m a_nx^n\)。

可列項相加的求和式稱為級數。在和式 \(\sum_{n=0}^\infty a_nx^n\) 中，每項均為非負整數次冪函數乘常數係數，這種形式的級數稱為冪級數。

研究多項式算術時先考慮較簡單的多項式，冪級數概念僅用於方便理解。到了數學分析中會進一步研究冪級數的斂散性。

環、域及其衍生結構的一般定義詳見羣論簡介。

對於一般環 \(R\)，定義 \(R\) 上的 多項式環（polynomial ring）\(R[x]\)。

每個元素 \(f\) 稱為 \(R\) 上的 多項式（polynomial），可表示為

\[ f=\left<f_0,f_1,f_2,\cdots,f_n\right>\quad(f_0,f_1,f_2,\cdots,f_n\in R) \]

換言之，我們將多項式直接定義為係數序列。也可以表示為

\[ f(x)=f_0+f_1x+f_2x^2+\cdots+f_nx^n \]

此處我們認為 \(x\) 只是一個 形式符號，一個對係數位置的標識符。

如果我們還允許無窮項的存在，即

\[ f(x)=f_0+f_1x+f_2x^2+\cdots \]

則可得到 形式冪級數環（formal power series ring）\(R[[x]]\)，其中的每個元素 \(f\) 稱為 形式冪級數（formal power series），以下簡稱冪級數。

多項式的度

對於一個多項式 \(f(x)\)，稱其最高次項的次數為該多項式的 度（degree），也稱次數，記作 \(\operatorname{deg}{f}\)。

多項式的乘法

最核心的操作是兩個多項式的乘法，即給定多項式 \(f(x)\) 和 \(g(x)\)：

\[ \begin{alignedat}{3} f(x)&=a_0+a_1x+\dots+a_nx^n\quad \quad &(1)\\ g(x)&=b_0+b_1x+\dots+b_mx^m\quad \quad &(2) \end{alignedat} \]

要計算多項式 \(Q(x)=f(x)\cdot g(x)\)：

\[ \boxed {Q(x) = \sum \limits_ {i = 0} ^ n \sum \limits_ {j = 0 } ^ m a_i b_j x ^ {i + j}} = c_0 + c_1 x + \dots + c_ {n + m} x ^ {n + m} \]

多項式或冪級數的乘法，滿足結合律，關於加法滿足分配律。若 \(R\) 為交換環或幺環，乘法相應的有交換律和單位元。

若 \(R\) 上存在 \(2^n\) 次單位根，快速傅里葉變換允許我們在 \(O(n2^n)\) 而不是 \(O(2^{2n})\) 的時間內計算兩個 \(2^n\) 次多項式的乘積。

複合

定義 \(R[[x]]\) 中元素 \(f\) 的乘方為

\[ f^1=f,f^k=f^{k-1}\times f \]

在此基礎上，定義 \(R[[x]]\) 中元素 \(f,g\) 的複合為

\[ (f\circ g)(x)=f(g(x))=f_0+\sum_{k=1}^{+\infty}f_kg^k(x) \]

我們規定 \(f\circ g\) 存在當且僅當 \(f\) 為有限項或 \(g_0=0\)，這樣就不涉及 \(R\) 上的極限了。

\(\circ\) 滿足結合律（\((f\circ g)\circ h\) 和 \(f\circ (g\circ h)\) 均存在時），不滿足交換律。\(R\) 為幺環時 \(\circ\) 存在單位元 \(1\times x\)。

FFT 可行時，有限項多項式的複合有 \(O((n\log n)^{1.5})\) 的算法，但此算法常數較大，實戰中往往 \(O(n^2)\) 的一種「分塊 FFT」算法具有更好的表現。

導數

儘管一般環甚至未必存在極限，
我們依然可以定義形式冪級數的 形式導數（formal derivative）為

\[ \left(\sum_{k=0}^{+\infty}f_kx^k\right)'=\sum_{k=1}^{+\infty}kf_kx^{k-1} \]

其中

\[ kf_k=\underbrace{f_k+f_k+\cdots+f_k}_{k \text{個} f_k} \]

基本求導法則——加法法則、乘法法則、鏈式法則（複合允許的情況下）依然是正確的。

如果 \(R\) 上允許作除法，同樣可以類似定義形式冪級數的 形式不定積分（formal indefinite integral）。

乘法逆元

根據例子

\[ \dfrac{1}{1-x}=1+x+x^2+\cdots \]

可以知道，多項式的倒數是能展開為無窮級數的。存在倒數，當且僅當常數項不為 \(0\)，並且倒數也滿足常數項不為 \(0\)。

因此定義：對於形式冪級數 \(f\)，若 \(f_0\not=0\)，其 乘法逆元（multiplicative inversion）\(f^{-1}\) 為另一形式冪級數，滿足

\[ f\times f^{-1}=f^{-1}\times f=1 \]

用形式冪級數乘法定義展開該式，可得 \(f^{-1}\) 係數的遞推式

\[ f^{-1}_0=\dfrac{1}{f_0},f^{-1}_n=\dfrac{-1}{f_0}\sum_{k=0}^{n-1}f^{-1}_kf_{n-k} \]

直接用遞推式計算前 \(n\) 項是 \(O(n^2)\) 的，運用 FFT 可得到 \(O(n\log n)\) 的算法。

注

容易發現，\(f(x)\) 的倒數就是 \(\frac{1}{f(x)}\) 的無窮項麥克勞林展開（在 \(x=0\) 處的無窮項泰勒展開）。

常見的冪級數展開式

在數學分析中，在某點處或某區間上若干階可導的一元函數可以在相應範圍進行多項式展開，一般統稱為泰勒展開，如果在 \(0\) 處展開，也稱為麥克勞林展開。

如果無窮階可導，則可以進行冪級數展開。最常見的還是在 \(0\) 處展開。

在複變函數中，一些函數在奇點上雖然不能進行泰勒展開，但是可以進行洛朗展開。

下列等式只在冪級數收斂時成立，在不收斂時不成立。這裏只寫出展開式，不討論收斂域。

基本的展開式有以下兩個，指數函數和冪函數：

\[ \mathrm{e}^x=1+x+\frac{1}{2!}x^2+\ldots+\frac{1}{n!}x^n+\ldots \]

\[ (1+x)^a=1+ax+\frac{a(a-1)}{2!}x^2+\ldots+\frac{a(a-1)\ldots(a-n+1)}{n!}x^n+\ldots \]

更多的展開式經常由上述兩個變形得到。比如正餘弦函數由指數函數代入複數得到：

\[ \cos x=1-\frac{1}{2!}x^2+\frac{1}{4!}x^4+\ldots+\frac{(-1)^n}{(2n)!}x^{2n}+\ldots \]

\[ \sin x=x-\frac{1}{3!}x^3+\frac{1}{5!}x^5+\ldots+\frac{(-1)^n}{(2n+1)!}x^{2n+1}+\ldots \]

對數和反正切、反正弦函數由積分得到：

\[ \frac{1}{1+x}=1-x+x^2+\ldots+{(-1)}^n x^n+\ldots \]

\[ \ln(1+x)=x-\frac{1}{2}x^2+\frac{1}{3}x^3+\ldots+\frac{{(-1)}^{n-1}}{n}x^n+\ldots \]

\[ \frac{1}{1+x^2}=1-x^2+x^4+\ldots+{(-1)}^n x^{2n}+\ldots \]

\[ \arctan x=x-\frac{1}{3}x^3+\frac{1}{5}x^5+\ldots+\frac{{(-1)}^{n}}{2n+1}x^{2n+1}+\ldots \]

\[ \frac{1}{\sqrt{1+x}}=1-\frac{1}{2}x+\frac{3}{8}x^2+\ldots+{(-1)}^n\frac{(2n)!}{{(n!)}^2 4^n} x^{n}+\ldots \]

\[ \frac{1}{\sqrt{1-x^2}}=1+\frac{1}{2}x^2+\frac{3}{8}x^4+\ldots+\frac{(2n)!}{{(n!)}^2 4^n} x^{2n}+\ldots \]

\[ \arcsin x=x+\frac{1}{6}x^3+\frac{3}{40}x^5+\ldots+\frac{(2n)!}{{(n!)}^2(2n+1)4^n} x^{2n+1}+\ldots \]

複合逆

複合逆（compound inversion）即反函數概念在形式冪級數環上的推廣。

對於滿足 \(f_0=0\) 且 \(f_1\not=0\) 的形式冪級數 \(f\)，其複合逆為滿足 \(g(f(x))=f(g(x))=x\) 的形式冪級數 \(g\)。由拉格朗日反演可得對於任意整數 \(n,k\) 有

\[ n[x^n]f^k=k[x^{n-k}]\left(\dfrac{x}{g}\right)^n \]

式中記號 \([x^k]f(x)\) 表示 \(f(x)\) 在 \(x^k\) 處的係數。

多項式整除

對於多項式 \(f(x)\) 和多項式 \(g(x)\)，如果存在一個多項式 \(h(x)\)，使得：

\[ f(x)=g(x)h(x) \]

則多項式 \(g(x)\) 整除多項式 \(f(x)\)。

顯而易見，多項式 \(g(x)\) 整除多項式 \(f(x)\)，當且僅當 \(g(x)\) 的根全部為 \(f(x)\) 的根，並且在 \(g(x)\) 中的重數不超過在 \(f(x)\) 中的相應重數。

多項式的餘數和商

對於多項式 \(f(x), g(x)\)，存在唯一的 \(Q(x), R(x)\) 滿足：

\[ \begin{aligned} f(x) &= Q(x) g(x) + R(x) \\ \operatorname{deg}{R} &< \operatorname{deg}{g} \end{aligned} \]

當 \(\operatorname{deg}{f} \ge \operatorname{deg}{g}\) 時有 \(\operatorname{deg}{Q} = \operatorname{deg}{f} - \operatorname{deg}{g}\)，否則有 \(Q(x) = 0\)。我們稱 \(Q(x)\) 為 \(g(x)\) 除 \(f(x)\) 的 商（quotient），\(R(x)\) 為 \(g(x)\) 除 \(f(x)\) 的 餘數（remainder）。

模多項式

模多項式是多項式環的子環，由多項式環除以同餘的等價關係得到。

在上文提到的帶餘除法中，多項式 \(f(x)\) 與它的餘式 \(R(x)\) 在模多項式 \(g(x)\) 的意義下同餘。

\[ f(x) \equiv R(x) \pmod{g(x)} \]

這個同餘式也意味着，對於多項式 \(g(x)\) 的任意一個根 \(x_0\)，代入 \(f(x)\) 和 \(R(x)\) 中，得到的點值相同。即：

\[ f(x_0)=R(x_0) \]

並且，如果根 \(x_0\) 在多項式 \(g(x)\) 中的重數是 \(k\)，即 \((x-x_0)^k\) 整除 \(g(x)\)，則對任意大於等於 \(0\) 小於 \(k\) 的整數 \(t\)，有：

\[ f^{t}(x_0)=R^{t}(x_0) \]

這裏的記號表示 \(t\) 階導數。

模多項式同餘可以應用於冪級數。一個無限項的冪級數，可以在模具體的多項式情形下，和一個有限項的多項式同餘。例如：

\[ 1+x+x^2+x^3+\ldots \equiv 1+x+\ldots+x^{n-1} \pmod{x^n} \]

顯然剩餘的所有項都被 \(x^n\) 整除，因此模 \(x^n\) 的操作等價於「截斷」，將無窮項的冪級數截斷到前 \(n\) 項，直接將更高位的信息丟失。

在一些特定的情況下，也可以模其他的多項式，下文將解釋相應情況。

多項式的多點求值和插值

多項式的多點求值（multi-point evaluation） 即給出一個多項式 \(f(x)\) 和 \(n\) 個點 \(x_{1}, x_{2}, \dots, x_{n}\)，求

\[ f(x_{1}), f(x_{2}), \dots, f(x_{n}) \]

多項式的插值（interpolation） 即給出 \(n+1\) 個點

\[ (x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{n}, y_{n}) \]

求一個 \(n\) 次多項式 \(f(x)\) 使得這 \(n+1\) 個點都在 \(f(x)\) 上。

這兩種操作的實質就是將多項式在 係數表示 和 點值表示 間轉化。多點求值將多項式的係數表示轉為點值表示，插值將多項式的點值表示轉為係數表示。

注

按照冪級數的觀點看，多點求值相當於將無窮項的信息「壓縮」到有限個點值表示，因此丟失了一些信息，而插值相當於還原到相應次數的係數表示。

編程常見的求值與插值，例如離散傅里葉變換（及其逆變換）等等，選擇的 \(n+1\) 個點重數均為 \(1\)，即兩兩不同，免去求導的麻煩。

這種「壓縮」只保證了在 \(n+1\) 個點上的一致。根據上文對模多項式同餘的解釋，如果冪級數 \(f(x)\) 經過在 \(x_0\) 到 \(x_n\) 點處求值再插值，得到多項式 \(R(x)\)，則作多項式：

\[ g(x)=(x-x_0)\ldots(x-x_n) \]

就有：

\[ f(x) \equiv R(x) \pmod{g(x)} \]

由於 \(R(x)\) 的次數嚴格小於 \(g(x)\)，所以利用求值與插值求出的 \(R(x)\) 就是餘式。因此在這種情況下，如果冪級數在根處可以求值，就可以模多項式。一個反例例如：

\[ \frac{1}{1-x}=1+x+x^2+x^3+\ldots \]

在 \(x=1\) 處不可求值，因此級數 \(1+x+x^2+x^3+\ldots\) 不能模多項式 \(x-1\)。

由於冪級數的任意階導數，在 \(0\) 處的值總是存在，因此模 \(x^n\) 始終可以計算，與上文「截斷」的意義一致。離散傅里葉變換（及其逆變換）相當於模多項式 \(x^n-1\)。

因式分解和歐幾里得

初等數論中的許多結論可以推廣到多項式上。

複數域上，由代數基本定理可得，對於 \(n\) 次多項式 \(f\)，方程

\[ f(x)=0 \]

有且僅有 \(n\) 個解（重根按重數計）。

於是 \(f(x)\) 在複數域內可唯一因式分解為如下形式

\[ a(x-x_1)^{c_1}(x-x_2)^{c_2}\cdots(x-x_m)^{c_m} \]

\[ c_1+c_2+\cdots+c_m=n,x_1,x_2,\cdots,x_m \text{ 互不相同} \]

此時類比正整數的最大公因數，可得多項式的 最大公因式
（greatest common divisor, gcd）。其可用歐幾里得算法求解

\[ \gcd(f,0)=f,\gcd(f,g)=\gcd(g,f\bmod g) \]

該性質可以推廣到較為一般的情況：

對於任意域 \(P\) 上的多項式環 \(P[x]\)，
多項式均可唯一因式分解，且可用歐幾里得算法計算最大公因式。需要注意的是，對於一般環上的多項式，該結論未必成立。

歐幾里得算法成立時，可用擴展歐幾里得給出不定方程

\[ f(x)P(x)+g(x)Q(x)=\gcd(f(x),g(x)) \]

的一組特解 \((P(x),Q(x))\)，並用裴蜀定理判斷不定方程

\[ f(x)P(x)+g(x)Q(x)=h(x) \]

的可解性。

HALF-GCD 允許我們在 \(O(n\log^2 n)\) 時間內計算多項式歐幾里得。

模多項式的乘法逆元

在模多項式 \(h(x)\) 意義下，冪級數 \(f(x)\) 有時存在逆元。逆元就是冪級數 \(f(x)\) 的倒數模多項式 \(h(x)\) 得到的餘式。

這個定義也等價於，對於多項式 \(f(x)\)，若存在 \(g(x)\) 滿足：

\[ \begin{aligned} f(x) g(x) & \equiv 1 \pmod{h(x)} \end{aligned} \]

則稱 \(g(x)\) 為 \(f(x)\) 在模 \(h(x)\) 意義下的 逆元（inverse element）。當多項式歐幾里得允許時，逆元存在當且僅當 \(\gcd(f,g)=1\)。

模多項式 \(h(x)\) 意義下逆元總是唯一的。如果多項式 \(f(x)\) 的次數也小於 \(h(x)\)，則得到的 \(g(x)\) 與 \(f(x)\) 互為逆元。

考慮「截斷」的概念，一般把模 \(x^n\) 意義下的逆元記作 \(f^{-1}(x)\)，也是後文默認使用的逆元概念。如果不加説明，逆元的模就是指 \(x^n\)。

注

一個問題是，可不可以用各種插值變換，直接求解「逆元」，比如計算：

\[ IDFT\left(\frac{DFT(1)}{DFT(f(x))}\right) \]

答案是否定的，不可以這樣做。根據上文的解釋，這裏利用離散傅里葉變換（及其逆變換）直接求出的逆元是模多項式 \(x^n-1\) 的逆元，不是通常的模多項式 \(x^n\) 的逆元。並且，由於原多項式在各點值處可能為 \(0\)，這個求解未必可以進行。

生成函數

生成函數（generating function），又稱母函數，是一種形式冪級數，其每一項的係數可以提供關於這個序列的信息。

生成函數有許多不同的種類，但大多可以表示為單一的形式：

\[ F(x)=\sum_n a_nk_n(x) \]

其中 \(k_n(x)\) 被稱為核函數。不同的核函數會導出不同的生成函數，擁有不同的性質。舉個例子：

普通生成函數：\(k_n(x)=x^n\)。
指數生成函數：\(k_n(x)=\dfrac{x^n}{n!}\)。
狄利克雷生成函數：\(k_n(x)=\dfrac{1}{n^x}\)。

參考資料與拓展閲讀

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用