本文作者为 JustinRochester。

目录地址

上一篇

下一篇

多项式的相关定义

多项式的来源

算法竞赛中常说的多项式，其含义与数学上的表达有一些区别。

狭义上，我们一般认为多项式是一个形如 \(\displaystyle F(x)=\sum_{i=0}^n f_ix^i\) 的函数。我们可以用一个长为 \(n+1\) 的数组表示这个多项式的各项系数。

而广义上，我们认为多项式是一个形如 \(\displaystyle F(x)=\sum_i f_ix^{e_i}\) 的函数，无所谓 \(e_i\) 是否互不相同，也无所谓 \(e_i\) 是自然数还是负数（但一般会要求是整数），甚至无所谓这个求和到底是有限项的求和还是无限项的。

大部分情况下，我们并不关心这个多项式在各点的函数值，这往往不重要（这也是为什么我们不关心是否是无限项求和）。很大部分情况下，我们会将一些与组合计数有关的数列“编码”至多项式的系数。

例如对于斐波那契数列，\(fib_n= \begin{cases} \begin{aligned} n&,n\leq 1\\ fib_{n-1}+fib_{n-2}&,n>1\\ \end{aligned} \end{cases}(n\geq 0)\) ，我们可以将其编码至多项式的系数上：\(\displaystyle F(x)=\sum_{i=0}^\infty fib_i x^i\)

根据斐波那契数列的规则我们可以得到：\(\displaystyle F(x)=0+x+\sum_{i=2}^\infty (fib_{i-1}+fib_{i-2})x^i=x+\sum_{i=2}^\infty fib_{i-1}x^i+\sum_{i=2}^\infty fib_{i-2}x^i\)

而 \(\displaystyle \sum_{i=2}^\infty fib_{i-1}x^i=x\sum_{i=1}^\infty fib_i x^i=x(F(x)-0), \sum_{i=2}^\infty fib_{i-2}x^i=x^2\sum_{i=0}^\infty fib_ix^i=x^2F(x)\)

因此我们得到：\(F(x)=x+xF(x)+x^2F(x)\) 进而得到 \(\displaystyle F(x)={x\over 1-x-x^2}\)

于是我们将所有的斐波那契数列“编码”到了多项式上

还记得吗？我们并不关心多项式在各点的函数值，因此我们也不关心这个函数的敛散性，它只是个“形式”。因此，也有人称呼它为形式幂级数。

当然，上述斐波那契数列“编码”得到的多项式写成了一个很简洁的函数形式。但是对于大部分组合计数的数列，往往并不能写成这种“封闭”的形式。

好在，我们也对是否能写成“封闭”的形式没有要求，我们仅对是否能写成 \(\displaystyle \sum_i f_ix^i\) （这里的 \(i\) 可以是负数，下同）有要求。

多项式的基本概念

我们称，多项式 \(\displaystyle F(x)=\sum_i f_ix^i\) 中，次数最高的非零项次数为该多项式的度，记为 \(\deg F\)。

如 \(\displaystyle F(x)=1+x+x^2, \deg F=2\) 。

特别的，我们认为 \(\displaystyle F(x)=\sum_{i=-\infty}^{+\infty} f_ix^i\) 和 \(\displaystyle F(x)=\sum_{i=c}^{+\infty} f_ix^i\) 的多项式度为 \(+\infty\) 。

而对于 \(F(x)=0\) ，我们认为 \(\deg F=-\infty\) 。