【算法•日更•第二十九期】基础多项式

阳光穿透心脏的1/2处 2023-06-03 02:51 38阅读 0赞

▎前言

小编相当的菜，这篇博客难度稍高，所以有些可能不会带有证明，博客中更多的是定义。

我们将要学到的东西：

*  环和域
 *  多项式
 *  卷积
 *  多项式乘法
 *  多项式点值表示
 *  多项式的根
 *  单位根

▎环和域

先来说什么是域。

简单的说，很多数字他们在一起能保证互相加减乘除这群数字中的数，仍能得到这群数字中的数（运算封闭），那么这些数字称为域。

当然，域中的数字通常是无限多个的。

那么环是什么，对比来看，域支持加减乘除运算封闭，而环只支持加和乘运算封闭。

也就是说域属于环，而域是特殊的环。

正因为域的特殊，所以域具有更多的性质，所以我们之后研究的多项式均与域相关，所以环在本篇博客中不是很重要。

常见域与环举例：

常见域：有理数域Q，实数域R，复数域C都是域。

常见环：整数集就是环。

因为整数集中除法是不封闭的，因为整数除以整数说不定会有小数，而小数不属于整数。

▎多项式

设R是一个环，a0，a1，…，an都是R中的元素，且an≠0，规定x0=1，那么我们把：

![1551435-20190801133839148-1345590453.png][]

称为R上n次多项式。

这个多项式是在环上定义的，但是我们后续使用的多项式，一律是**域上的多项式**。

▎卷积

数字与数字的乘法的结果叫做积。

而**向量乘向量**的结果叫做**卷积**。

那么什么是向量，如果你不想知道就看下一段（对后续内容没有妨碍），向量就是有方向的量，也就是说这种量不仅有数字那样的**值**，也有方向。如平面直角坐标系中的坐标，就是向量（方向就是原点到这个点的方向）。

当然，向量可以存很多个数，类似于数组，所以之后提到的向量a，b，如果没有特殊说明，可以认为是多项式a和多项式b的系数存储的数组。

利用我们平时多项式乘多项式的过程，我们可以得出以下结论：

对于向量a，b，令

![1551435-20190801135011219-1060713618.png][]

那么c就是向量a与b的积（这只是个定义，不需要证明什么的）。

▎多项式乘法

设这里有两个多项式f(x)和g(x)（项数分别是n和m），那么我们易得：

![1551435-20190801135253940-1607258459.png][]

其中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次单位根。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11280417.html

[1551435-20190801133839148-1345590453.png]: /images/20230601/43847996ffa94a3cadf077395a2253b1.png
[1551435-20190801135011219-1060713618.png]: /images/20230601/56064c109c5c4a78b9b69c9b485535c3.png
[1551435-20190801135253940-1607258459.png]: /images/20230601/6fca714ff7264601ad6f48c93d66db9e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，38人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法•日更•第四十九期】双系统

　　双系统是实现使用两个系统的第二个方式，众所周知，虚拟机是个好东西，但是有众多不便的地方：　　![1551435-20190818220507151-1405964119

爱被打了一巴掌/ 2023年06月03日 02:52/ 0 赞/ 63 阅读

相关【算法•日更•第二十九期】基础多项式

▎前言　　小编相当的菜，这篇博客难度稍高，所以有些可能不会带有证明，博客中更多的是定义。　　我们将要学到的东西：环和域多项式卷积多项式

阳光穿透心脏的1/2处/ 2023年06月03日 02:51/ 0 赞/ 39 阅读

相关【算法•日更•第二十八期】图论：强连通+Tarjan算法（一）

▎前言　　一直都想学习这个东西，以为很难，结果发现也不过如此。　　只要会些图论的基础就可以了。 ▎强连通 ☞『定义』　　既然叫强连通，那么一定具有很强的连通性。

港控/mmm°/ 2023年06月03日 02:50/ 0 赞/ 47 阅读

相关【算法•日更•第二十七期】基础python

▎前言　　看到这个题目，你一定会很好奇，为什么学打NOIP的要学习python？其实python对我们是很有用的！　　NOIP虽然不支持使用python提交代码，但是在

系统管理员/ 2023年06月03日 02:50/ 0 赞/ 17 阅读

相关【算法•日更•第二十六期】非常基础的数论

　　一说到基础数论，那么我们就从整除那套理论开始谈起。 -------------------- ▎整除 ☞『定义』　　如果a能把b整除，也就是没有余数，则我们称a整

逃离我推掉我的手/ 2023年06月03日 02:50/ 0 赞/ 44 阅读

相关【算法•日更•第二十五期】万能算法（一）：搜索+？

▎前言　　看到这个标题，你是不是倍感疑惑，为什么会是搜索+，而不是搜索，会不会是小编打错的，其实本篇博客将会让你看到搜索的各种玩法。 ▎前置技能 ☞『基础知识』　　

墨蓝/ 2023年06月03日 02:50/ 0 赞/ 23 阅读

相关【算法•日更•第二十四期】二分查找和二分答案的区别

▎前置技能　　[二分（戳这里了解）][Link 1]和[分治（戳这里了解）][Link 2]。 ▎前言　　想必你已经学会了二分，但是你真的知道二分查找和二分答案的区别

古城微笑少年丶/ 2023年06月03日 02:50/ 0 赞/ 29 阅读

相关【算法•日更•第二十期】构造分治

▎什么是分治？ ☞『定义』　　分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简

向右看齐/ 2023年06月03日 02:50/ 0 赞/ 44 阅读

相关【算法•日更•第十九期】动态规划：RMQ问题

▎前言　　首先先来说一下RMB是什么，当然是人民币啦。　　今天我们要学的这个东西不一般，叫做RMQ问题，那么它和RMB有什么关系呢？待小编细细说来。 ▎前置技能：动态

水深无声/ 2023年06月03日 02:49/ 0 赞/ 169 阅读

相关【算法•日更•第二十六期】非常基础的数论

　　一说到基础数论，那么我们就从整除那套理论开始谈起。 -------------------- ▎整除 ☞『定义』　　如果a能把b整除，也就是没有余数，则我们称a整

曾经终败给现在/ 2021年10月29日 07:16/ 0 赞/ 263 阅读