简述
如果你手上有一堆散点，然后你可以用这个公式拟合出一个函数：
\[ f(x) = \sum_{i = 1}^n y_i \prod_{j \neq i}^n \frac{x – x_j}{x_i – x_j} \]
Continue reading →多项式开根
原理推导
按照多项式求逆中倍增的思想，可以写出这样的推导：假设我们已知在\(\pmod {x^{\lceil \frac{n}{2} \rceil}}\)求得\(B'(x)\)为当前的解，现在要步进至\(\pmod x^n\)，那么我们可以写出
BZOJ 3456:城市规划题解
题面
注意：这道题在 BZOJ 上是权限题，我是在 JZOJ 上做的。
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过, 阿狸的国家有\(n\)个城市，现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通。
为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案, 如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出\(n\)个点的简单（无重边无自环）无向连通图数目。
由于这个数字可能非常大，你只需要输出方案数 mod 1004535809(479 * 2 ^21 + 1) 即可。
多项式求逆
前置技能
FFT、NTT、多项式乘法。
原理推理
现在我们有一个这样的式子：
\[ A(x)B(x) \equiv C(x) \ (mod \ x^n) \]
现在我们已知\(B(x), C(x)\)的信息，而我们计算答案的时候需要用\(A(x)\)进行运算。这个时候，我们需要求出\(B(x)\)的逆元。多项式求逆元，我们一般是用倍增的方式来求解。假如我们有\(B(x)\)在模\(x^{\lceil \frac{x}{2} \rceil}\)意义下的逆元\(D(x)\)：
多项式乘法 & 快速傅立叶变换
简述
在信息学竞赛中，多项式乘法出现得非常的多，朴素算法的时间复杂度为\(O(n^2)\)，成为了许多毒瘤出题人卡指数的地方。所以，用快速傅立叶变换（FFT, Fast Fourier Transform）来优化多项式乘法是很有必要的。接下来，我会由浅入深地来介绍这两者与其之间的关系。