多项式101-点值表示法与系数表示法学习笔记

· · 个人记录

多项式是什么？

形如f(x)=\sum a_ix^i的函数，展开来就像：

f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots

多项式有什么用？

前置知识

复数(WorkInProgress...)
单位根(WorkInProgress...)

多项式的系数表示法

多项式的系数表示法就是我们平常经常使用的方式，用n个数a_i表示一个函数f(x)

f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots

应该很好理解吧，这个就不做过多赘述了

多项式的点值表示法

我们在小学初中的时候都学过，我给你3个点，你可以计算出一个且只有一个二次函数通过全部三个点。
所以对于多项式来说，我们计算其点值表示法的时候就是维护n个点(x_i,y_i)表示这个多项式通过全部这n个点
注意：此时表示出来的函数是最高次数n-1的函数。
一般在使用 FFT 的时候我们取的n个点的横坐标是\omega_n^k，用一个长度为n的数组存下来。
一般在使用 NTT 的时候我们取的n个点的横坐标是g_n^p，同样直接用长度为n的数组存下来即可。

点值表示法有什么好处呢？

对于两个函数f(x)和g(x)我们可以很快地求出h(x)=f(x)g(x)，因为我们只用将这n个点相乘即可，复杂度是\Theta(n)的。
对于一个函数套函数的操作来说，也可以\Theta(n)计算出来转换后的点值具体表达。

下一篇：多项式102-FFT学习笔记
下一篇：多项式103-NTT学习笔记