各种多项式操作的 n^2 递推

zszz，使用 NTT 可以在 \(\mathcal O(n\log n)\) 的时间内求出两个多项式的卷积、以及一个多项式的 \(\text{inv},\ln,\exp,\text{sqrt}\) 等，但是如果模数不是 NTT 模数（譬如 \(10^9+7\)）并且复杂度允许 \(\mathcal O(n^2)\) 实现上述操作，那么再使用 \(n\log n\) 的 NTT 优化版多项式全家桶就不合适了，因此我们也要懂得如何暴力 \(n^2\) 递推。

多项式乘法

这个就过于弱智了吧……直接枚举对应位然后往它们的和的地方贡献即可，这个幼儿园就学过了（

多项式求逆

假设 \(B\) 为 \(A\) 的逆元，那么显然有 \(AB=1\)，即

\[\sum\limits_{i=0}^nA_iB_{n-i}=[n=0]
\]

即

\[A_0B_n=-\sum\limits_{i=1}^nA_iB_{n-i}(n\ge 1)
\]

\[B_n=-\dfrac{1}{A_0}\sum\limits_{i=1}^nA_iB_{n-i}
\]

边界 \(B_0=\dfrac{1}{A_0}\)

多项式 \(\ln\)

假设 \(B(x)=\ln A(x)\)，那么注意到在我们 NTT 逆元时，我们采用了求导，再积分回去的做法，即 \(B’(x)=\dfrac{A’(x)}{A(x)}\)，因此我们只需对 \(A(x)\) 求一遍逆，再积分回去即可，不过事实上还有更简洁（常数更小）的推法，具体来说

\[B'(x)A(x)=A'(x)
\]

\[(n+1)A_{n+1}=\sum\limits_{i=0}^nB_{i+1}(i+1)A_{n-i}
\]

\[B_{n+1}(n+1)A_0=A_{n+1}(n+1)-\sum\limits_{i=0}^{n-1}B_{i+1}(i+1)A_{n-i}
\]

\[B_{n+1}=\dfrac{A_{n+1}(n+1)-\sum\limits_{i=1}^{n}iB_iA_{n+1-i}}{A_0(n+1)}
\]

\[B_n=\dfrac{nA_n-\sum\limits_{i=1}^{n-1}iB_iA_{n-i}}{A_0n}
\]

一般在取 \(\ln\) 时默认 \(A_0=1\)，因此一般来说上式也可以写作

\[B_n=A_n-\dfrac{1}{n}\sum\limits_{i=1}^{n-1}iB_iA_{n-i}
\]

多项式 \(\exp\)

根据 \(\exp\) 的性质，\(\exp’(A(x))=\exp(A(x))A(x)\)，因此假设 \(B(x)=\exp(A(x))\)，那么显然有

\[B'(x)=B(x)A'(x)
\]

\[B_{n+1}(n+1)=\sum\limits_{i=0}^nB_{n-i}A_{i+1}(i+1)
\]

\[B_{n+1}=\dfrac{1}{n+1}\sum\limits_{i=0}^nB_{n-i}A_{i+1}(i+1)
\]

\[B_n=\dfrac{1}{n}\sum\limits_{i=1}^{n}B_{n-i}A_ii
\]

多项式 \(\exp_{\le k}\)

对于多项式 \(A(x)\)，定义其 \(\exp_{\le k}\) 为

\[\sum\limits_{i=0}^k\dfrac{A^i(x)}{i!}
\]

因此 \(\exp(A(x))\) 也可视为 \(\exp_{\le\infty}\)

那么怎么暴力求这东西呢？我们假设 \(B(x)=\sum\limits_{i=0}^k\dfrac{A^i(x)}{i!}\)，那么

\[B'(x)=\sum\limits_{i=0}^k\dfrac{iA^{i-1}(x)A'(x)}{i!}
\]

\[B'(x)=\sum\limits_{i=0}^k\dfrac{A^{i-1}(x)A'(x)}{(i-1)!}
\]

\[B'(x)=A'(x)\sum\limits_{i=0}^{k-1}\dfrac{A^{i}(x)}{i!}
\]

我们惊奇地发现 \(\sum\limits_{i=0}^{k-1}\dfrac{A^i(x)}{i!}=B(x)-\dfrac{A^k(x)}{k!}\)

于是

\[B'(x)=A'(x)(B(x)-\dfrac{A^k(x)}{k!})
\]

我们假设 \(C(x)=\dfrac{A^k(x)}{k!}\)，那么

\[B_{n+1}(n+1)=\sum\limits_{i=0}^nA_{i+1}(i+1)(B_{n-i}-C_{n-i})
\]

\[B_{n+1}=\dfrac{1}{n+1}\sum\limits_{i=0}^nA_{i+1}(i+1)(B_{n-i}-C_{n-i})
\]

\[B_n=\dfrac{1}{n}\sum\limits_{i=1}^nA_ii(B_{n-i}-C_{n-i})
\]

边界条件 \(B_0=\sum\limits_{i=0}^k\dfrac{A_0^i}{i!}\)

巴特西