浅谈多项式算法

Preface

多项式算法可以延伸出很多重要的定理, 无论实在 OI 界 还是 数学 界 都有着十分重要的地位

Start up

设两个多项式

$$\begin{split} f(x)&=a_0+a_1x+a_2x^2+\cdots+a_nx^n\\ g(x)&=b_0+b_1x+b_2x^2+\cdots+b_nx^n \end{split}$$

首先我们要引入几个基本定理

系数表示

我们主要研究的是多项式的系数, 所以要引入系数表示法
显然易得, 我们可以直接拿系数来表示一个多项式: $f(x)=\{a_0,a_1,a_2,\cdots,a_n\}$

点值表示

那么能否转化为点值表示呢, 毕竟点值有很多优良性质可以用

我们用 $n+1$ 个点 $\{x_0,x_1,\cdots,x_n\}$ 带入 $f(x)$ 可以得到: $\{(x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n))\}$

显然, 如果他们不是唯一确定的, 我们无法进行"稳定的相互转换", 进而无法使用点值表示法求解多项式问题.

那么如何证明点值表示法的唯一确定性?

证明

当然你用范德蒙行列式证明也行, 然而我不会

考虑反证法.

假设现在 $f(x)\neq g(x)$($\exist\ a_k\neq b_k, k=0,1,\cdots,n$)
但是, 有 $\{(x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n))\}=\{(x_0,g(x_0)),(x_1,g(x_1)),\cdots,(x_n,g(x_n))\}; x_i\neq x_j\neq 0, i\neq j; i,j=0,1,\cdots,n$
意思是: 现在无法保证 $f(x),g(x)$ 全部的系数都相等(他们是不同的多项式), 但是他们的点值表示法是相等的

简单情况

首先考虑非常简单的情况( $n=2$ )
带入 $\{ x_0, x_1 \}$ 可以得到

$$\begin{cases} a_0+a_1x_0+a_2x_0^2=b_0+b_1x_0+b_2x_0^2\\ a_0+a_1x_1+a_2x_1^2=b_0+b_1x_1+b_2x_1^2 \end{cases}$$

整理得

$$\begin{cases} (a_0-b_0)+(a_1-b_1)x_0+(a_2-b_2)x_0^2=0\\ (a_0-b_0)+(a_1-b_1)x_1+(a_2-b_2)x_1^2=0 \end{cases}$$

上下相减得

$$(a_1-b_1)(x_0-x_1)+(a_2-b_2)(x_0^2-x_1^2)=0$$

不难发现 $(x_0^2-x_1^2)=(x_0-x_1)(x_0+x_1)$ 又 $(x_0-x_1)\neq 0$
不难得到 $(a_1-b_1)+(a_2-b_2)(x_0+x_1)=0$
同理得到 $(a_1-b_1)+(a_2-b_2)(x_1-x_2)=0$
上下相减 $(a_2-b_2)(x_0+x_2)=0$
又因为 $a_k\neq b_k, x_i\neq x_j\neq 0; i,j,k\in \{0,1,2\}$
即 $(a_2-b_2)\neq 0, (x_0+x_2)\neq 0$
由此产生矛盾

复杂情况

简单情况想通后就简单了, 把 $n+1$ 个式子每次用第 $k$ 个式子 减去第 $k+1$ 个式子, 然后套用因式定理逐步消掉一些简单因式, 得到 $n$ 个式子, 最终逐步得到 $1$ 个因式相乘组成的式子, 找出矛盾即可

简单来说就是一直上下相减, 当然过程量有点复杂, 但是 因式定理 出来的一连串加法是可以在下一轮上下相减中消去的, 所以最后可以得到 $(a_n-b_n)(x_0+x_n)=0$
自己简单拿 $n=4$ 的情况推一下就理解了, 一般形式的证明有点繁琐我就不写了