很早就开始学了吧 一直没有写学习笔记..

candy? 的博客写的很不错啊

多项式一系列操作复杂度\(T(n) = T(n/2) + \mathcal O(nlogn) = \mathcal O(nlogn)\)

多项式求逆

倍增的思想

已知\(A(x)B_0(x) \equiv 1 \pmod {x^n}\)

求\(B(x)\)满足\(A(x)B(x) \equiv 1 \pmod {x^{2n}}\)

多项式有逆元的前提是常数项有逆元

两式相减 然后平方展开 左右同时乘上\(A(x)\)可以得到

\[B(x) \equiv B_0(x) (2 - B_0(x)A(x))\pmod {x^{2n}}\]

多项式开方

同样倍增

已知\(B_0^{2}(x) \equiv A(x) \pmod {x^n}\)

求\(B(x)\)满足\(B^2(x) \equiv A(x) \pmod {x^{2n}}\)

\[ (B_0^{2}(x) - A(x)) ^ 2 \equiv 0 \pmod {x^{2n}}\]

\[ (B_0^{2}(x) + A(x)) ^ 2 \equiv 4 B_0^{2}(x) A(x) \pmod {x^{2n}}\]

\[ (\frac {B_0^{2}(x) + A(x)}{2B_0(x)}) ^ 2 \equiv A(x)\pmod {x^{2n}}\]

同样需要多项式求逆元

多项式求ln

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

\[B'(x) = \frac {A'(x)} {A(x)}\]

求一下导积分积回去

牛顿迭代

已知\(g(x)\)求\(f(x)\) 满足 \(g(f(x)) = 0\)

已知前\(n\)项\(f(x) \equiv f_0(x) \pmod {x^n}\)

对\(g(f_0(x))\)泰勒展开 .. 这里感觉好强

得到

\[f(x) = f_0(x) - \frac {g(f_0(x))}{g'(f_0(x))}\]

多项式求exp

定义\(f(x) = e^{A(x)}\)

以及 \(g(f(x)) = ln(f(x)) - A(x) = 0\)

代入牛顿迭代式子中去

\[f(x) = f_0(x) - \frac {ln(f_0(x)) - A(x)}{1/(f_0(x))}\]

整理得

\[f(x) = f_0(x) (1 - ln(f_0(x)) + A(x))\]

bzoj3456

定义\(G(x)\) 为无向(不一定连通)图数目 有

\[G(x) = \sum_{n \ge 0} 2^{C_n^2} \frac {x^n} {n!}\]

根据指数生成函数 设\(F(x)\)为无向连通图数目 有

\[G(x) = \sum_{n \ge 0} \frac {F(x) ^ n} {n!}\]

因为无向图是由若干无向连通图组成的集合

于是\(G=e^{F}\) \(F = ln(G)\)

求一个ln就好了