多项式公式总结

拉格朗日插值

普通插值

\[ f(x) =\sum ^{n}_{i=0}y_{i}\prod _{j\neq i}\dfrac{x-x_{j}}{x_{i}-x_{j}} \]

线性插值

\[ \sum ^{n}_{i=0}y_{i}\dfrac{\prod ^{n}_{j=0}(x-j) }{i!(n-i) !(x-i) }\cdot (-1) ^{n-i} \]

注意特判 \(0\leq x\leq n\)。

FFT 的推导

\[ \begin{aligned} f(x) &=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-1}x^{n-1}\\ g(x) &=a_{0}+a_{2}x+a_{4}x^{2}+\ldots +a_{n-2}x^{\frac{n}{2}-1}\\ h(x) &=a_{1}+a_{3}x+a_{5}x^{2}+\ldots +a_{n-1}x^{\frac{n}{2}-1}\\ f(\omega _{n}^{k}) &=g(\omega_{n}^{2k}) +\omega _{n}^{k}h(\omega_{n}^{2k}) \\ &=g(\omega_{\frac n 2}^k)+\omega _{n}^{k}h(\omega_{\frac n 2}^{k}) \end{aligned} \]

多项式全家桶

求逆

\[ \begin{aligned}\dfrac{1}{u(x) }&=f(x) \\ F(u(x) ) &=\dfrac{1}{u(x) }-f(x) =0\\ u(x) &=u_{0}(x) -\dfrac{ F(u_{0}(x) ) } {F'(u_{0}(x) )} \\ &=2u_{0}(x) -u_{0}^{2}(x) f(x) \end{aligned} \]

ln

\[ \begin{aligned} u(x) &=\ln f(x) \\ u'(x) &=f'(x)\ln'f(x) \\ &=\dfrac{f'(x) }{f(x) }\\ u(x) &=\int \dfrac{f'(x) }{f(x) }\mathrm{d}x\end{aligned} \]

exp

\[ \begin{aligned}u(x) &=\exp \{ f(x) \} \\ \ln u(x) &=f(x) \\ F(u(x) ) &=\ln u(x) -f(x) \\ u(x) &=u_{0}(x) -\dfrac{F(u_{0}(x) ) }{F'(u_{0}(x) ) }\\ &=u_{0}(x) (1+f(x) -\ln u_0(x) ) \end{aligned} \]

开根

\[ \begin{aligned}u(x) &=\sqrt{f(x) }\\ F(u(x) ) &=u^{2}(x) -f(x) \\ u(x) &=u_{0}(x) -\dfrac{F(u_{0}(x) ) }{F'(u_{0}(x) ) }\\ &=\dfrac{1}{2}(u_{0}(x) +\dfrac{f(x) }{u_{0}(x) }) \end{aligned} \]

快速幂

\[ f^{k}(x) =\exp \{ k\ln f(x) \} \]

取模

\[ \begin{aligned}n&=\deg (f(x) ) ,m=\deg (g(x) ) \\ \tilde f(x) &=\sum ^{n}_{i=0}a_{i}x^{n-i}\\ &=x^{n}\sum ^{n}_{i=0}a_{i}x^{-i}\\ &=x^{n}f(\dfrac{1}{x}) \\ &\space\space\space\space\space\space\space\space\space\space\space\space\Downarrow \\ f(x) &=g(x) h(x) +r(x) \\ f(\dfrac{1}{x}) &=g(\dfrac{1}{x}) h(\dfrac{1}{x}) +r(\dfrac{1}{x}) \\ x^{n}f(\dfrac{1}{x}) &=x^{m}g(\dfrac{1}{x}) x^{n-m}h(\dfrac{1}{x}) +x^{n}r(\dfrac{1}{x}) \\ \tilde f(x) &\equiv \tilde g(x) \tilde h(x) \pmod {x^{n-m+1}} \\\tilde h(x) &=\dfrac{\tilde f(x) }{\tilde g(x) }\bmod x^{n-m+1}\end{aligned} \]

多点求值

\[ \begin{aligned}f(x_{i}) &=f(x)\bmod(x-x_{i}) \\ L(x) &=f(x) \bmod\prod ^{mid}_{i=l}(x-x_i) \\ R(x) &=f(x) \bmod\prod ^{r}_{i=mid +1}(x-x_{i}) \\ f(x_{il}) &=L(x) \bmod(x-x_{i}) \\ f(x_{ir}) &=R(x) \bmod(x-x_{i})\end{aligned} \]

递归计算即可。

快速插值

\[ \begin{aligned}\pi (x) &=\prod ^{n}_{i=0}(x-x_{i}) \\ z_{i}&=\dfrac{y_{i}}{\prod _{j\neq i}(x_{i}-x_{j}) }=\dfrac{y_{i}}{\pi '(x_{i}) }\\ f(x) &=\sum ^{n}_{i=0}z_{i}\prod _{j\neq i}(x-x_{j}) \\ &=\pi (x) \sum ^{n}_{i=0}\dfrac{z_{i}}{x-x_{i}}\end{aligned} \]

常系数齐次线性递推

\[ f_{i}=\sum ^{k}_{j=1}a_{j}f_{i-j} \]

即求

\[ x^{n}\bmod(x^{k}-\sum ^{k-1}_{j=0}a_{k-j}x^{j}) \]

重要恒等式

\[ \begin{aligned} &\text{等比求和}:&&\sum_{i=0}^{n-1} x^i &&=& &\dfrac {1-x^n}{1-x}\\ &\text{等比级数 1}:&&\sum_{n=0}^{\infty} x^n &&=& &\dfrac 1{1-x}\\ &\text{等比级数 2}:&&\sum_{n=0}^{\infty} (n+1)x^n &&=& &\dfrac 1{(1-x)^2}\\ &\text{等比级数 3}:&&\sum_{n=0}^{\infty} \dbinom {n+k-1}{k-1} x^n &&=& &\dfrac 1{(1-x)^k}\\ &\text{指数函数}:&&\sum_{n=0}^{\infty} \dfrac {1}{n!} x^n &&=&& \exp\{x\}\\ &\text{幂函数}:&&\sum_{n=0}^{\infty} \dbinom \alpha n a^nb^{\alpha-n} x^n &&=& &(ax+b)^\alpha\\ &\text{对数函数}:&&\sum_{n=1}^{\infty} \dfrac {1}{n} x^n &&=&& -\ln(1-x)\\ &\text{上升幂转普通幂}:&&\sum_{i=0}^{n} \begin{bmatrix} n\\ i \end{bmatrix}x^i &&=&& x^\overline n\\ &\text{下降幂转普通幂}:&&\sum_{i=0}^{n} (-1)^i\begin{bmatrix} n\\ i \end{bmatrix}x^i &&=&& x^\underline n\\ &\text{普通幂转上升幂}:&&\sum_{i=0}^{n} (-1)^i\begin{Bmatrix} n\\ i \end{Bmatrix}x^\overline i &&=&& x^n\\ &\text{普通幂转下降幂}:&&\sum_{i=0}^{n} \begin{Bmatrix} n\\ i \end{Bmatrix}x^\underline i &&=&& x^n\\ \end{aligned} \]