标签：连乘 专题 个点 变换 多项式 快速
最近accoders天天出多项式科技题，我一道都不会，场场罚坐。气死我了， 我也要学科技。
杂项
Lagrange 插值
有 \(n\) 个点，我们试图确定一个 \(n - 1\) 次多项式。
设这 \(n\) 个点是 \((x_i, y_i )\)
这个多项式就是：
\(f(x) =\sum_{i = 1}^{n}{ y_i \prod_{i \neq j} \frac{x - x_j}{x_i - x_j }}\)
证明：
这是一个 $n - 1$ 次多项式。右侧只有 $x$ 是变量，其余均为常数，共乘了 $n - 1$ 次。
这个函数中 $n$ 个点与原函数重合。代入 $x = x_k$ ，我们发现只有 $k = i$ 时候,连乘为 $1$, 其余情况为 $0$
因此，我们证明了该多项式与原多项式相等。
优化：连续整数取值。
变换
FFT 快速傅里叶变换
NTT 快速数论变换
FWT 快速沃尔什变换
标签：连乘,
专题,
个点,
变换,
多项式,
快速
From： https://www.cnblogs.com/cdsidi/p/16792842.html