多项式

多项式的度

若存在 $g(x)$ 满足：

f(x)g(x) \equiv 1 \pmod{x^n}

则称 $g(x)$ 为 $f(x)$ 在模 $x^n$ 意义下的逆元， $g(x)=f^{-1}(x)$ 。

对于多项式 $f(x),g(x)$ ，存在唯一的 $Q(x),R(x)$ 满足：

f(x)=Q(x)g(x)+R(x)\\ \deg R < \deg g

\ln(1-f(x))=-\sum_{i=1}^{+\infty} \frac{f^i(x)}{i}\\ \exp f(x)=\sum_{i=0}^{+\infty}\frac{f^{i}(x)}{i!}

我们希望构造一个函数 $f(x)$ 过点 $P_1(x_1,y_1),P_2(x_2,y_2)\cdots,P_n(x_n,y_n)$ 。

可以先构造 $n$ 个函数 $f_i(x)$ ，使得对于 $f_i(x)$ ，其经过 $P_1(x_1,0),\cdots,P_{i-1}(x_{i-1},0)，P_i(x_i,y_i),P_{i+1}(x_{i+1},0)\cdots P_n(x_n,0)$ 。

那么我们就可以令

f_i(x)=\frac{y_i}{\prod_{j\not=i} (x_i-x_j)} \prod_{j\not=i} (x-x_j)

可以得出 $f(x)=\sum_{i=1}^n f_i(x)$ ，即：

f(x)=\sum_{i=1}^n y_i \prod_{j\not=i} \frac{x-x_j}{x_i-x_j}

如果 $x_1,x_2\cdots x_n$ 为连续整数 $1,\cdots,n$ ，预处理阶乘，有 $O(n)$ 的做法。