朴素多项式算法 - \(O(n^2)\) 合集
我们并不需要 NTT，就算需要，也只是用来优化乘法。
多项式求逆
对于多项式 \(\sum a_i x^i\) 我们需要构造出一个多项式 \(\sum b_i x^i\) 使得：
\[\begin{cases}
a_0 b_0 = 1 \\
\sum_{i = 0}^k a_i b_{k - i} = 0 & k \ge 1
\end{cases}
\]
首先 \(b_0\) 是好知道的，剩下的 \(\sum_{i = 0}^k a_i b_{k - i} = 0\) 将 \(b_k\) 那一项单独拆出来：
\[a_0 b_k = - \sum_{i = 1}^k a_i b_{k - i}
\]
如果我们已知 \(b_{[0, k)}\)，那么就可以通过上式推出 \(b_k\)。
同时，这可以利用半在线卷积优化到 \(O(n \log^2 n)\)。
多项式 \(\ln\)
考虑：
\[B(x) = \ln A(x) \iff B'(x) = \frac {A'(x)}{A(x)}
\]
那么我们只需要多项式求导和求逆和积分即可。
或者有另外一种简单的公式：
\[B'(x) A(x) = A'(x) \iff \left(\sum_{i = 0}^{n - 1} (i + 1)b_{i + 1} x^i \right) \left(\sum_{i = 0}^n a_i x^i\right) = \sum_{i = 0}^{n - 1} (i + 1) a_{i + 1} x^i
\]
将 \([x^n]\) 提出来：
\[(k + 1)a_{k+ 1} = \sum_{i = 0}^k (i + 1)b_{i + 1} a_{k - i} \iff k a_k = \sum_{i = 1}^k i b_i a_{k + 1 - i}
\]
将 \(b_k\) 单独提出来：
\[k a_1 b_k = k a_k - \sum_{i = 1}^{k - 1} i b_i a_{k + 1 - i}
\]
如果我们已知 \(b_{[1, k)}\)，那么就可以通过上式推出 \(b_k\)。
同样可以利用半在线卷积优化到 \(O(n \log^2 n)\)。
多项式 \(\exp\)
类似的考虑：
\[B(x) = e^{A(x)} \iff \ln B(x) = A(x) \iff \frac {B'(x)}{B(x)} = A'(x) \iff B'(x) = A'(x) B(x)
\]
将系数提取出来：
\[(k + 1) b_{k + 1} = \sum_{i = 0}^k (i + 1) a_{i + 1} b_{k - i}
\]
将下标平移一下：
\[k b_k = \sum_{i = 1}^k i a_i b_{k - i}
\]
如果我们已知 \(b_{[0, k)}\)，那么就可以通过上式推出 \(b_k\)。
同样可以利用半在线卷积优化到 \(O(n \log^2 n)\)（Ctrl-C + Ctrl-V
半在线卷积
看了怎么久，来学学半在线卷积吧！
半在线卷积其实就是……多项乘法上的 cdq 分治！
没啥好说的，呱。
作者有话说
看看多项式板子有多长，比线粒体还长！用 \(O(n^2)\) 代码短，不容易错，还不受模数的限制！
反正省选什么的也不会考 NTT，但是会考多项式，所以学一学总是好的。