多项式的逆¶
数学中很多元素在一定条件下都存在逆元。多项式的逆元是什么呢？
从乘法逆元出发，一个简单的想法是，多项式 g(x) 是 f(x) 的逆元当且仅当 f(x)\cdot g(x)=0。遗憾的是，只有当 f(x) 只有常数项时才存在这样的多项式 g(x)，否则 g(x) 必须为无穷的幂级数。因此，我们在模的意义下考虑多项式的逆，得到多项式逆元的定义：
f(x) 的逆元 g(x) 是一个满足 f(x)\cdot g(x)\equiv 1\pmod{x^n} 的多项式。
分别用 f_{0..n-1} 和 g_{0..n-1} 来表示 f(x) 和 g(x) 的系数，把 h(x)=f(x)\cdot g(x) 写下来：
h(x)\cdot g(x)\equiv \sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{i}f_{j}g_{i-j}\cdot x^{i}
要满足上面的定义，h(x)\cdot g(x) 就只有 x^0 项为 1，其余项为 0，即
f_0g_0=1
和
\forall i\ge 1: \sum\limits_{j=0}^{i}f_{j}g_{i-j}=0
这两个条件都成立，g(x) 才是 f(x) 的逆元。由第一个条件可知，若 f(x) 的常数项为 0，则 g(x) 一定不存在（0 不存在逆元）。若 f(x) 的常数项不为零，是否就一定存在 g(x) 满足第二个条件呢？
考虑把上面的式子视作一个 n 元一次方程组，f_{0..n-1} 是已知系数，g_{0..n-1} 是未知数。条件给出了 n 个次数上升的等式，方程组一定有解，而且有唯一解。
\begin{cases}f_0g_0&=1\\f_0g_1+f_1g_0&=0\\f_0g_2+f_1g_1+f_2g_0&=0\\f_0g_3+f_1g_2+f_2g_1+f_3g_0&=0\\ \ldots\\ f_0g_{n-1}+f_1g_{n-2}+f_2g_{n-3}+\ldots+f_{n-1}g_0&=0\end{cases}
也就是说， f(x) 在模 x^n 意义下存在逆元，当且仅当 f(x) 的常数项非零；若 f(x) 存在逆元，它一定只有一个逆元。
根据上述方程组求逆的时间复杂度是 O(n^2)，更快的 O(n\log n) 算法请参考 Newton's Method。