演算法 日更 第二十九期 基礎多項式

2022-11-24 17:31:57 字數 1682 閱讀 5580

▎前言

我們將要學到的東西:

▎環和域

先來說什麼是域。

簡單的說,很多數字他們在一起能保證互相加減乘除這群數字中的數,仍能得到這群數字中的數(運算封閉),那麼這些數字稱為域。

當然,域中的數字通常是無限多個的。

那麼環是什麼,對比來看,域支援加減乘除運算封閉,而環只支援加和乘運算封閉。

也就是說域屬於環,而域是特殊的環。

常見域與環舉例:

常見域:有理數域q,實數域r,複數域c都是域。

常見環:整數集就是環。

因為整數集中除法是不封閉的,因為整數除以整數說不定會有小數,而小數不屬於整數。

▎多項式

設r是一個環,a0,a1,…,an都是r中的元素,且an≠0,規定x0=1,那麼我們把:

稱為r上n次多項式。

這個多項式是在環上定義的,但是我們後續使用的多項式,一律是域上的多項式

▎卷積數字與數字的乘法的結果叫做積。

向量乘向量的結果叫做卷積

那麼什麼是向量,如果你不想知道就看下一段(對後續內容沒有妨礙),向量就是有方向的量,也就是說這種量不僅有數字那樣的,也有方向。如平面直角座標系中的座標,就是向量(方向就是原點到這個點的方向)。

當然,向量可以存很多個數,類似於陣列,所以之後提到的向量a,b,如果沒有特殊說明,可以認為是多項式a和多項式b的係數儲存的陣列。

利用我們平時多項式乘多項式的過程,我們可以得出以下結論:

對於向量a,b,令

那麼c就是向量a與b的積(這只是個定義,不需要證明什麼的)。

▎多項式乘法

設這裡有兩個多項式f(x)和g(x)(項數分別是n和m),那麼我們易得:

其中c是a與b的卷積。

顯然,直接計算的時間複雜度是o(nm)。

▎多項式點值表示

我們先來思考:多項式的表示方法有幾種?

兩種,一種是係數表示法,一種是點值表示法。

係數表示法:按照一定的順序(例如按x的次數升序)排列,那麼我們只要知道每一項對應的係數,那麼我們就可以確定唯一的多項式。

點值表示法:我們可以取一個x的值並帶入,就會得到唯一的f值,就像函式一樣,我們需要n+1對點對( xk, f(xk) )就可以確定唯一的多項式f(x)。

知道了點值表示法後,我們設f(x), g(x) 為次數分別為 n, m 的多項式,那麼就有n+m+1個互 不相同的點 x0, x1, . . . , xn+m。

若我們已經知道了f(x), g(x),那麼我們就可以以較少的時間複雜度得到f(x) g(x),當然,加法也是這樣。

▎多項式的根

設域f屬於域k,f(x)是f上的多項式,α是k中的元素,若f(α)=0,那麼我們稱α為f(x)的一個根。

因此f(x)的根不一定在f中。

▎單位根

多項式xn−1的根稱為n次單位根。