From b18c710bdfad2551c595af15679dab5c027d3f71 Mon Sep 17 00:00:00 2001
From: Tri-solaris <trisolaris@126.com>
Date: Fri, 1 Mar 2019 22:48:38 +0800
Subject: [PATCH] add serval pages about polynomial

---
 docs/math/poly-div-mod.md                       | 130 ++++++++++++++++++++++
 docs/math/poly-inv.md                           |  75 +++++++++++++
 docs/math/poly-ln-exp.md                        | 137 ++++++++++++++++++++++++
 docs/math/poly-multipoint-eval-interpolation.md | 102 ++++++++++++++++++
 docs/math/poly-newton.md                        |  95 ++++++++++++++++
 docs/math/poly-sqrt.md                          |  78 ++++++++++++++
 docs/math/poly.md                               |  62 +++++++++++
 7 files changed, 679 insertions(+)
 create mode 100755 docs/math/poly-div-mod.md
 create mode 100755 docs/math/poly-inv.md
 create mode 100755 docs/math/poly-ln-exp.md
 create mode 100644 docs/math/poly-multipoint-eval-interpolation.md
 create mode 100644 docs/math/poly-newton.md
 create mode 100755 docs/math/poly-sqrt.md

diff --git a/docs/math/poly-div-mod.md b/docs/math/poly-div-mod.md
new file mode 100755
index 00000000..64f537bc
--- /dev/null
+++ b/docs/math/poly-div-mod.md
@@ -0,0 +1,130 @@
+# Description
+
+&emsp;&emsp;给定多项式 $f\left(x\right),g\left(x\right)$,求 $g\left(x\right)$ 除 $f\left(x\right)$ 的商 $Q\left(x\right)$ 和余数 $R\left(x\right)$.
+
+# Method
+
+&emsp;&emsp;发现若能消除 $R\left(x\right)$ 的影响则可直接[**多项式求逆**](../poly-inv)解决.
+
+&emsp;&emsp;考虑构造变换
+
+$$f^{R}\left(x\right)=x^{\operatorname{deg}{f}}f\left(\frac{1}{x}\right)$$
+
+&emsp;&emsp;观察可知其实质为反转 $f\left(x\right)$ 的系数.
+
+&emsp;&emsp;设 $n=\operatorname{deg}{f},m=\operatorname{deg}{g}$.
+
+&emsp;&emsp;将 $f\left(x\right)=Q\left(x\right)g\left(x\right)+R\left(x\right)$ 中的 $x$ 替换成 $\frac{1}{x}$ 并将其两边都乘上 $x^{n}$,得到:
+
+$$\begin{aligned}
+    f\left(\frac{1}{x}\right)&=x^{n-m}Q\left(x\right)x^{m}g\left(x\right)+x^{n-m+1}x^{m-1}R\left(x\right)\\
+    f^{R}\left(x\right)&=Q^{R}\left(x\right)g^{R}\left(x\right)+x^{n-m+1}R^{R}\left(x\right)
+\end{aligned}$$
+
+&emsp;&emsp;注意到上式中 $R^{R}\left(x\right)$ 的系数为 $x^{n-m+1}$,则将其放到模 $x^{n-m+1}$ 意义下即可消除 $R^{R}\left(x\right)$ 带来的影响.
+
+&emsp;&emsp;又因 $Q^{R}\left(x\right)$ 的次数为 $\left(n-m\right)<\left(n-m+1\right)$,故 $Q^{R}\left(x\right)$ 不会受到影响.
+
+&emsp;&emsp;则:
+
+$$f^{R}\left(x\right)\equiv Q^{R}\left(x\right)g^{R}\left(x\right)\pmod{x^{n-m+1}}$$
+
+&emsp;&emsp;使用多项式求逆即可求出 $Q\left(x\right)$,将其反代即可得到 $R\left(x\right)$.
+
+&emsp;&emsp;时间复杂度 $O\left(n\log{n}\right)$.
+
+# Code
+
+??? " `poly-div-mod.cpp` "
+
+    ```cpp
+    using Z=int;
+    using mZ=long long;
+    using poly_t=Z[mxdg];
+    using poly=Z*const;
+
+    inline int calcpw2(const int&n){
+        int t=1;
+        for(;t<n;t<<=1);
+        return t;
+    }
+    inline void cp(const Z*const&sl,const Z*const&sr,Z*const&dl,Z*const&dr){
+        std::copy(sl,sr,dl);
+        if(sr-sl<dr-dl)
+            std::fill(dl+(sr-sl),dr,0);
+    }
+
+    void polydiv(const poly&f,const int&n,const poly&g,const int&m,poly&Q,poly&R){
+        static poly_t div_t;
+
+        const int res=n-m+1;
+        const int deg1=calcpw2(res+res);
+
+        std::reverse_copy(g,g+m,Q);
+        if(m<deg1)
+            std::fill(Q+m,Q+deg1,0);
+        polyinv(Q,div_t,res);
+
+        std::reverse_copy(f+m-1,f+n,Q);
+        std::fill(Q+res,Q+deg1,0);
+
+        DFT(Q,deg1);DFT(div_t,deg1);
+        for(int i=0;i!=deg1;++i)
+            Q[i]=(mZ)Q[i]*div_t[i]%p;
+        IDFT(Q,deg1);
+
+        std::reverse(Q,Q+res);
+        std::fill(Q+res,Q+deg1,0);
+
+        const int deg2=calcpw2(n);
+
+        cp(Q,Q+res,R,R+deg2);
+        cp(g,g+m,div_t,div_t+deg2);
+
+        DFT(R,deg2);DFT(div_t,deg2);
+        for(int i=0;i!=deg2;++i)
+            R[i]=(mZ)R[i]*div_t[i]%p;
+        IDFT(R,deg2);
+
+        for(int i=0;i!=m;++i)
+            R[i]=sub(f[i],R[i]);
+        std::fill(R+m-1,R+deg2,0);
+    }
+
+    void polymod(const poly&f,const int&n,const poly&g,const int&m,poly&R){
+        static poly_t mod_t;
+
+        const int res=n-m+1;
+        const int deg1=calcpw2(res+res);
+
+        std::reverse_copy(g,g+m,R);
+        if(m<deg1)
+            std::fill(R+m,R+deg1,0);
+        polyinv(R,mod_t,res);
+
+        std::reverse_copy(f+m-1,f+n,R);
+        std::fill(R+res,R+deg1,0);
+
+        DFT(R,deg1);DFT(mod_t,deg1);
+        for(int i=0;i!=deg1;++i)
+            R[i]=(mZ)R[i]*mod_t[i]%p;
+        IDFT(R,deg1);
+
+        std::reverse(R,R+res);
+        std::fill(R+res,R+deg1,0);
+
+        const int deg2=calcpw2(n);
+
+        cp(g,g+m,mod_t,mod_t+deg2);
+
+        DFT(R,deg2);DFT(mod_t,deg2);
+        for(int i=0;i!=deg2;++i)
+            R[i]=(mZ)R[i]*mod_t[i]%p;
+        IDFT(R,deg2);
+
+        for(int i=0;i!=m;++i)
+            R[i]=sub(f[i],R[i]);
+        std::fill(R+m-1,R+deg2,0);
+    }
+    ```
+
diff --git a/docs/math/poly-inv.md b/docs/math/poly-inv.md
new file mode 100755
index 00000000..9b6789f0
--- /dev/null
+++ b/docs/math/poly-inv.md
@@ -0,0 +1,75 @@
+# Description
+
+&emsp;&emsp;给定多项式 $f\left(x\right)$,求 $f^{-1}\left(x\right)$.
+
+# Methods
+
+## 倍增法
+
+&emsp;&emsp;首先,易知
+
+$$\left[x^{0}\right]f^{-1}\left(x\right)=\left(\left[x^{0}\right]f\left(x\right)\right)^{-1}$$
+
+&emsp;&emsp;假设现在已经求出了 $f\left(x\right)$ 在模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的逆元 $f^{-1}_{0}\left(x\right)$.
+&emsp;&emsp;有:
+
+$$\begin{aligned}
+	f\left(x\right)f^{-1}_{0}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
+	f\left(x\right)f^{-1}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
+	f^{-1}\left(x\right)-f^{-1}_{0}\left(x\right)&\equiv 0 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}
+\end{aligned}$$
+
+&emsp;&emsp;两边平方可得:
+
+$$f^{-2}\left(x\right)-2f^{-1}\left(x\right)f^{-1}_{0}\left(x\right)+f^{-2}_{0}\left(x\right)\equiv 0 \pmod{x^{n}}$$
+
+&emsp;&emsp;两边同乘 $f\left(x\right)$ 并移项可得:
+
+$$f^{-1}\left(x\right)\equiv f^{-1}_{0}\left(x\right)\left(2-f\left(x\right)f^{-1}_{0}\left(x\right)\right) \pmod{x^{n}}$$
+
+&emsp;&emsp;递归计算即可.
+
+&emsp;&emsp;时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+## Newton's Method
+
+&emsp;&emsp;参见 [**Newton's Method**](../poly-newton/#inv).
+
+# Code
+
+??? " `poly-inv.cpp` "
+
+    ```cpp
+    inline void cp(const Z*const&sl,const Z*const&sr,Z*const&dl,Z*const&dr){
+        std::copy(sl,sr,dl);
+        if(sr-sl<dr-dl)
+            std::fill(dl+(sr-sl),dr,0);
+    }
+
+    void polyinv(const poly&h,poly&f,const int&n){
+        static poly_t inv_t;
+        std::fill(f,f+n+n,0);
+        f[0]=fpow(h[0],p-2);
+        for(int t=1;(1<<t)<=n;++t){
+            const int deg1=1<<t,deg2=deg1<<1;
+            cp(h,h+deg1,inv_t,inv_t+deg2);
+
+            DFT(f,deg2);DFT(inv_t,deg2);
+            for(int i=0;i!=deg2;++i)
+                f[i]=(mZ)f[i]*sub(2ll,(mZ)inv_t[i]*f[i]%p)%p;
+            IDFT(f,deg2);
+
+            std::fill(f+deg1,f+deg2,0);
+        }
+    }
+    ```
+
+
+
+# Examples
+
+1. 有标号简单无向连通图计数:「BZOJ 3456」城市规划
+
+
diff --git a/docs/math/poly-ln-exp.md b/docs/math/poly-ln-exp.md
new file mode 100755
index 00000000..a5a1ede4
--- /dev/null
+++ b/docs/math/poly-ln-exp.md
@@ -0,0 +1,137 @@
+# Description
+
+&emsp;&emsp;给定多项式 $f\left(x\right)$,求模 $x^{n}$ 意义下的 $\ln{f\left(x\right)}$ 与 $\exp{f\left(x\right)}$.
+
+# Methods
+
+## 普通方法
+
+---
+
+&emsp;&emsp;首先,对于多项式 $f\left(x\right)$,若 $\ln{f\left(x\right)}$ 存在,则由其[定义](../#ln-exp),其必须满足:
+
+$$\left[x^{0}\right]f\left(x\right)=1$$
+
+&emsp;&emsp;对 $\ln{f\left(x\right)}$ 求导再积分,可得:
+
+$$\begin{aligned}
+    \left(\ln{f\left(x\right)}\right)'&\equiv\frac{f'\left(x\right)}{f\left(x\right)}&\pmod{x^{n}}\\
+    \ln{f\left(x\right)}&\equiv\int\frac{f'\left(x\right)}{f\left(x\right)}&\pmod{x^{n}}
+\end{aligned}$$
+
+&emsp;&emsp;多项式的求导,积分时间复杂度为 $O\left(n\right)$,求逆时间复杂度为 $O\left(n\log{n}\right)$,故多项式求 $\ln$ 时间复杂度 $O\left(n\log{n}\right)$.
+
+---
+
+&emsp;&emsp;首先,对于多项式$f\left(x\right)$,若 $\exp{f\left(x\right)}$ 存在,则其必须满足:
+
+$$\left[x^{0}\right]f\left(x\right)=0$$
+
+&emsp;&emsp;否则 $\exp{f\left(x\right)}$ 的常数项不收敛.
+
+&emsp;&emsp;对 $\exp{f\left(x\right)}$ 求导,可得:
+
+$$\exp'{f\left(x\right)}\equiv\exp{f\left(x\right)}f'\left(x\right)\pmod{x^{n}}$$
+
+&emsp;&emsp;比较两边系数可得:
+
+$$\left(n+1\right)\left[x^{n}\right]\exp{f\left(x\right)}=\sum_{i=0}^{n}\left[x^{i}\right]\exp{f\left(x\right)}\left(n-i+1\right)\left[x^{n-i}\right]f\left(x\right)$$
+
+&emsp;&emsp;又 $\left[x^{0}\right]f\left(x\right)=0$,则:
+
+$$\left(n+1\right)\left[x^{n}\right]\exp{f\left(x\right)}=\sum_{i=0}^{n-1}\left[x^{i}\right]\exp{f\left(x\right)}\left(n-i+1\right)\left[x^{n-i}\right]f\left(x\right)$$
+
+&emsp;&emsp;使用分治 FFT 即可解决.
+
+&emsp;&emsp;时间复杂度 $O\left(n\log^{2}{n}\right)$.
+
+## Newton's Method
+
+&emsp;&emsp;使用 [**Newton's Method**](../poly-newton/#exp) 即可在 $O\left(n\log{n}\right)$ 的时间复杂度内解决多项式 $\exp$.
+
+# Code
+
+??? " `poly-ln-exp.cpp` "
+
+    ```cpp
+    using Z=int;
+    using mZ=long long;
+    using poly_t=Z[mxdg];
+    using poly=Z*const;
+
+    void polyder(const poly&f,poly&df,const int&n){
+        for(int i=1;i!=n;++i)
+            df[i-1]=(mZ)f[i]*i%p;
+        df[n-1]=0;
+    }
+
+    void polyint(const poly&f,poly&intf,const int&n){
+        for(int i=n-1;i;--i)
+            intf[i]=(mZ)f[i-1]*inv[i]%p;
+        intf[0]=0;
+    }
+
+    void polyln(const poly&h,poly&f,const int&n){
+        static poly_t ln_t;
+        assert(h[0]==1);
+        const int n2=n<<1;
+
+        polyder(h,f,n);
+        std::fill(f+n,f+n2,0);
+        polyinv(h,ln_t,n);
+
+        DFT(f,n2);DFT(ln_t,n2);
+        for(int i=0;i!=n2;++i)
+            f[i]=(mZ)f[i]*ln_t[i]%p;
+        IDFT(f,n2);
+
+        polyint(f,f,n);
+        std::fill(f+n,f+n2,0);
+    }
+
+    void polyexp(const poly&h,poly&f,const int&n){
+        static poly_t exp_t;
+        assert(h[0]==0);
+        std::fill(f,f+n+n,0);
+        f[0]=1;
+        for(int t=1;(1<<t)<=n;++t){
+            const int deg1=1<<t,deg2=deg1<<1;
+
+            polyln(f,exp_t,deg1);
+            exp_t[0]=sub(h[0]+1,exp_t[0]);
+            for(int i=1;i!=deg1;++i)
+                exp_t[i]=sub(h[i],exp_t[i]);
+            std::fill(exp_t+deg1,exp_t+deg2,0);
+
+            DFT(f,deg2);DFT(exp_t,deg2);
+            for(int i=0;i!=deg2;++i)
+                f[i]=(mZ)f[i]*exp_t[i]%p;
+            IDFT(f,deg2);
+
+            std::fill(f+deg1,f+deg2,0);
+        }
+    }
+    ```
+
+# Examples
+
+1. 计算 $f^{k}\left(x\right)$
+
+&emsp;&emsp;普通做法为多项式快速幂,时间复杂度 $O\left(n\log{n}\log{k}\right)$.
+
+&emsp;&emsp;当 $\left[x^{0}\right]f\left(x\right)=1$ 时,有:
+
+$$f^{k}\left(x\right)=\exp{\left(k\ln{f\left(x\right)}\right)}$$
+
+&emsp;&emsp;当 $\left[x^{0}\right]f\left(x\right)\neq 1$ 时,设 $f\left(x\right)$ 的最低次项为 $f_{i}x^{i}$,则:
+
+$$f^{k}\left(x\right)=f_{i}^{k}x^{ik}\exp{\left(k\ln{\frac{f\left(x\right)}{f_{i}x^{i}}}\right)}$$ 
+
+&emsp;&emsp;时间复杂度 $O\left(n\log{n}\right)$.
+
+
+
+
+
+
+
diff --git a/docs/math/poly-multipoint-eval-interpolation.md b/docs/math/poly-multipoint-eval-interpolation.md
new file mode 100644
index 00000000..015064d9
--- /dev/null
+++ b/docs/math/poly-multipoint-eval-interpolation.md
@@ -0,0 +1,102 @@
+# 多项式的多点求值
+
+## Description
+
+给出一个多项式 $f\left(x\right)$ 和 $n$ 个点 $x_{1},x_{2},...,x_{n}$,求
+
+$$f\left(x_{1}\right),f\left(x_{2}\right),...,f\left(x_{n}\right)$$
+
+## Method
+
+考虑使用分治来将问题规模减半.
+
+将给定的点分为两部分:
+
+$$\begin{aligned}
+	X_{0}&=\left\{x_{1},x_{2},...,x_{\left\lfloor\frac{n}{2}\right\rfloor}\right\}\\
+	X_{1}&=\left\{x_{\left\lfloor\frac{n}{2}\right\rfloor+1},x_{\left\lfloor\frac{n}{2}\right\rfloor+2},...,x_{n}\right\}
+\end{aligned}$$
+
+构造多项式
+
+$$g_{0}\left(x\right)=\prod_{x_{i}\in X_{0}}\left(x-x_{i}\right)$$
+
+则有 $\forall x\in X_{0}:g_{0}\left(x\right)=0$.
+
+考虑将 $f\left(x\right)$ 表示为 $g_{0}\left(x\right)Q\left(x\right)+f_{0}\left(x\right)$ 的形式,即:
+
+$$f_{0}\left(x\right)\equiv f\left(x\right)\pmod{g_{0}\left(x\right)}$$
+
+则有 $\forall x\in X_{0}:f\left(x\right)=g_{0}\left(x\right)Q\left(x\right)+f_{0}\left(x\right)=f_{0}\left(x\right)$,$X_{1}$ 同理.
+
+至此,问题的规模被减半,可以使用分治+多项式取模解决.
+
+时间复杂度
+
+$$T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log^{2}{n}\right)$$
+
+## Code
+
+~~啥?你问我要代码?不存在的,调了一万年现在还是 WA~~
+
+# 多项式的快速插值
+
+## Description
+
+给出一个 $n+1$ 个点的集合
+
+$$X=\left\{\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),...,\left(x_{n},y_{n}\right)\right\}$$
+
+求一个 $n$ 次多项式 $f\left(x\right)$ 使得其满足 $\forall\left(x,y\right)\in X:f\left(x\right)=y$.
+
+## Method
+
+仍然考虑使用分治来将问题规模减半.
+
+将给定的点分为两部分:
+
+$$\begin{aligned}
+	X_{0}&=\left\{x_{0},x_{1},...,x_{\left\lfloor\frac{n}{2}\right\rfloor}\right\}\\
+	X_{1}&=\left\{x_{\left\lfloor\frac{n}{2}\right\rfloor+1},x_{\left\lfloor\frac{n}{2}\right\rfloor+2},...,x_{n}\right\}
+\end{aligned}$$
+
+假设已经求出了 $X_{0}$ 中的点插值出的多项式 $f_{0}\left(x\right)$,考虑如何使其变为所求的 $f\left(x\right)$.
+
+构造多项式
+
+$$g_{0}\left(x\right)=\prod_{x_{i}\in X_{0}}\left(x-x_{i}\right)$$
+
+则有 $\forall\left(x,y\right)\in X_{0}:g_{0}\left(x\right)=0$.
+
+考虑将 $f\left(x\right)$ 表示为 $g_{0}\left(x\right)f_{1}\left(x\right)+f_{0}\left(x\right)$ 的形式.
+
+由于 $\forall\left(x,y\right)\in X_{0}:f\left(x\right)=g_{0}\left(x\right)f_{1}\left(x\right)+f_{0}\left(x\right)=f_{0}\left(x\right)=y$,故 $X_{0}$ 中的点都在 $f\left(x\right)$ 上.
+
+考虑构造 $f_{1}\left(x\right)$ 使得 $X_{1}$ 中的点也在 $f\left(x\right)$ 上,即:
+
+$$\forall\left(x,y\right)\in X_{1}:f_{1}\left(x\right)g_{0}\left(x\right)+f_{0}\left(x\right)=y$$
+
+变形可得:
+
+$$\forall\left(x,y\right)\in X_{1}:f_{1}\left(x\right)=\frac{y-f_{0}\left(x\right)}{g_{0}\left(x\right)}$$
+
+这样就得到了新的待插值点集合:
+
+$$X'_{1}=\left\{\left(x,\frac{y-f_{0}\left(x\right)}{g_{0}\left(x\right)}\right):\left(x,y\right)\in X_{1}\right\}$$
+
+递归对 $X'_{1}$ 插值出 $f_{1}\left(x\right)$ 即可.
+
+由于每次都需要多点求值求出新的待插值点集合 $X'_{1}$,时间复杂度为:
+
+$$T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\log^{2}{n}\right)=O\left(n\log^{3}{n}\right)$$
+
+## Code
+
+~~啥?你问我要代码?我多点求值都没过你问我要插值代码?~~
+
+
+
+
+
+
+
diff --git a/docs/math/poly-newton.md b/docs/math/poly-newton.md
new file mode 100644
index 00000000..9d39eb4b
--- /dev/null
+++ b/docs/math/poly-newton.md
@@ -0,0 +1,95 @@
+# Description
+
+&emsp;&emsp;给定多项式 $g\left(x\right)$,已知有 $f\left(x\right)$ 满足:
+
+$$g\left(f\left(x\right)\right)\equiv 0\pmod{x^{n}}$$
+
+&emsp;&emsp;求出模 $x^{n}$ 意义下的 $f\left(x\right)$.
+
+# Newton's Method
+
+&emsp;&emsp;考虑倍增.
+
+&emsp;&emsp;首先当 $n=1$ 时,$\left[x^{0}\right]g\left(f\left(x\right)\right)=0$ 的解需要单独求出.
+
+&emsp;&emsp;假设现在已经得到了模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的解 $f_{0}\left(x\right)$,要求模 $x^{n}$ 意义下的解 $f\left(x\right)$.
+
+&emsp;&emsp;将 $g\left(f\left(x\right)\right)$ 在 $f_{0}\left(x\right)$ 处进行泰勒展开,有:
+
+$$\sum_{i=0}^{+\infty}\frac{g^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}$$
+
+&emsp;&emsp;因为 $f\left(x\right)-f_{0}\left(x\right)$ 的最低非零项次数最低为 $\left\lceil\frac{n}{2}\right\rceil$,故有:
+
+$$\forall 2\leqslant i:\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}$$
+
+&emsp;&emsp;则:
+
+$$\sum_{i=0}^{+\infty}\frac{g^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv g\left(f_{0}\left(x\right)\right)+g'\left(f_{0}\left(x\right)\right)\left(f\left(x\right)-f_{0}\left(x\right)\right)\equiv 0\pmod{x^{n}}$$
+$$f\left(x\right)\equiv f_{0}\left(x\right)-\frac{g\left(f_{0}\left(x\right)\right)}{g'\left(f_{0}\left(x\right)\right)}\pmod{x^{n}}$$
+
+# Examples
+
+## <span id="inv">[多项式求逆](../poly-inv)</span>
+
+&emsp;&emsp;设给定函数为 $h\left(x\right)$,有方程:
+
+$$g\left(f\left(x\right)\right)=\frac{1}{f\left(x\right)}-h\left(x\right)\equiv 0\pmod{x^{n}}$$
+
+&emsp;&emsp;应用 Newton's Method 可得:
+
+$$\begin{aligned}
+    f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{\frac{1}{f_{0}\left(x\right)}-h\left(x\right)}{-\frac{1}{f_{0}^{2}\left(x\right)}}&\pmod{x^{n}}\\
+    &\equiv 2f_{0}\left(x\right)-f_{0}^{2}\left(x\right)h\left(x\right)&\pmod{x^{n}}
+\end{aligned}$$
+
+&emsp;&emsp;时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+## <span id="sqrt">[多项式开方](../poly-sqrt)</span>
+
+&emsp;&emsp;设给定函数为 $h\left(x\right)$,有方程:
+
+$$g\left(f\left(x\right)\right)=f^{2}\left(x\right)-h\left(x\right)\equiv 0\pmod{x^{n}}$$
+
+&emsp;&emsp;应用 Newton's Method 可得:
+
+$$\begin{aligned}
+    f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{f_{0}^{2}\left(x\right)-h\left(x\right)}{2f_{0}\left(x\right)}&\pmod{x^{n}}\\
+    &\equiv\frac{f_{0}^{2}\left(x\right)+h\left(x\right)}{2f_{0}\left(x\right)}&\pmod{x^{n}}
+\end{aligned}$$
+
+&emsp;&emsp;时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+## <span id="exp">[多项式 exp](../poly-exp)</span>
+
+&emsp;&emsp;设给定函数为 $h\left(x\right)$,有方程:
+
+$$g\left(f\left(x\right)\right)=\ln{f\left(x\right)}-h\left(x\right)\pmod{x^{n}}$$
+
+&emsp;&emsp;应用 Newton's Method 可得:
+
+$$\begin{aligned}
+    f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{\ln{f_{0}\left(x\right)}-h\left(x\right)}{\frac{1}{f_{0}\left(x\right)}}&\pmod{x^{n}}\\
+    &\equiv f_{0}\left(x\right)\left(1-\ln{f_{0}\left(x\right)+h\left(x\right)}\right)&\pmod{x^{n}}
+\end{aligned}$$
+
+&emsp;&emsp;时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+
+
+
+
+
+
+
+
+
+
+
+
+
diff --git a/docs/math/poly-sqrt.md b/docs/math/poly-sqrt.md
new file mode 100755
index 00000000..4800f2dc
--- /dev/null
+++ b/docs/math/poly-sqrt.md
@@ -0,0 +1,78 @@
+# Description
+
+&emsp;&emsp;给定多项式 $g\left(x\right)$,求 $f\left(x\right)$,满足:
+
+$$f^{2}\left(x\right)\equiv g\left(x\right) \pmod{x^{n}}$$
+
+# Methods
+
+## 倍增法
+
+&emsp;&emsp;假设现在已经求出了 $g\left(x\right)$ 在模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的平方根 $f_{0}\left(x\right)$,则有:
+
+$$\begin{aligned}
+	f_{0}^{2}\left(x\right)&\equiv g\left(x\right) &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
+	f_{0}^{2}\left(x\right)-g\left(x\right)&\equiv 0 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
+	\left(f_{0}^{2}\left(x\right)-g\left(x\right)\right)^{2}&\equiv 0 &\pmod{x^{n}}\\
+	\left(f_{0}^{2}\left(x\right)+g\left(x\right)\right)^{2}&\equiv 4f_{0}^{2}\left(x\right)g\left(x\right) &\pmod{x^{n}}\\
+	\left(\frac{f_{0}^{2}\left(x\right)+g\left(x\right)}{2f_{0}\left(x\right)}\right)^{2}&\equiv g\left(x\right) &\pmod{x^{n}}\\
+	\frac{f_{0}^{2}\left(x\right)+g\left(x\right)}{2f_{0}\left(x\right)}&\equiv f\left(x\right) &\pmod{x^{n}}\\
+	2^{-1}f_{0}\left(x\right)+2^{-1}f_{0}^{-1}\left(x\right)g\left(x\right)&\equiv f\left(x\right) &\pmod{x^{n}}
+\end{aligned}$$
+
+&emsp;&emsp;倍增计算即可.
+
+&emsp;&emsp;时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+&emsp;&emsp;还有一种常数较小的写法就是在倍增维护 $f\left(x\right)$ 的时候同时维护 $f^{-1}\left(x\right)$ 而不是每次都求逆.
+
+> 当 $\left[x^{0}\right]g\left(x\right)\neq 1$ 时,可能需要使用二次剩余来计算 $\left[x^{0}\right]f\left(x\right)$.
+
+## Newton's Method
+
+&emsp;&emsp;参见 [**Newton's Method**](../poly-newton/#sqrt).
+
+# Code
+
+??? " `poly-sqrt.cpp` "
+
+		```cpp
+		using Z=int;
+		using mZ=long long;
+		using poly_t=Z[mxdg];
+		using poly=Z*const;
+
+		inline void cp(const Z*const&sl,const Z*const&sr,Z*const&dl,Z*const&dr){
+			std::copy(sl,sr,dl);
+			if(sr-sl<dr-dl)
+				std::fill(dl+(sr-sl),dr,0);
+		}
+
+		void polysqrt(const poly&h,poly&f,const int&n){
+			static poly_t sqrt_t,inv_t;
+			std::fill(f,f+n+n,0);
+			f[0]=root(h[0],2);
+			for(int t=1;(1<<t)<=n;++t){
+				const int deg1=1<<t,deg2=deg1<<1;
+
+				polyinv(f,inv_t,deg1);
+				cp(h,h+deg1,sqrt_t,sqrt_t+deg2);
+
+				DFT(sqrt_t,deg2);DFT(inv_t,deg2);
+				for(int i=0;i!=deg2;++i)
+					sqrt_t[i]=(mZ)inv_t[i]*sqrt_t[i]%p;
+				IDFT(sqrt_t,deg2);
+
+				for(int i=deg1>>1;i!=deg1;++i)
+					f[i]=div2(sqrt_t[i]);
+				std::fill(f+deg1,f+deg2,0);
+			}
+		}
+		```
+
+# Examples
+
+1. [**「Codeforces Round #250」E. The Child and Binary Tree**](/「Codeforces-Round-250」E-The-Child-and-Binary-Tree/)
+
diff --git a/docs/math/poly.md b/docs/math/poly.md
index 8b137891..98da1ec5 100644
--- a/docs/math/poly.md
+++ b/docs/math/poly.md
@@ -1 +1,63 @@
+# Basic Concepts
+
+## 多项式的度
+
+&emsp;&emsp;对于一个多项式 $f\left(x\right)$,称其最高次项的次数为该多项式的**度(Degree)**,记作 $\operatorname{deg}{f}$.
+
+## <span id="inv">多项式的逆元</span>
+
+&emsp;&emsp;对于多项式 $f\left(x\right)$,若存在 $g\left(x\right)$ 满足:
+
+$$\begin{aligned}
+    f\left(x\right)g\left(x\right)&\equiv 1\pmod{x^{n}}\\
+    \operatorname{deg}{g}&\leqslant\operatorname{deg}{f}
+\end{aligned}$$
+
+&emsp;&emsp;则称 $g\left(x\right)$ 为 $f\left(x\right)$ 在模 $x^{n}$ 意义下的**逆元(Inverse Element)**,记作 $f^{-1}\left(x\right)$.
+
+## <span id="div-mod">多项式的余数和商</span>
+
+&emsp;&emsp;对于多项式 $f\left(x\right),g\left(x\right)$,存在**唯一**的 $Q\left(x\right),R\left(x\right)$ 满足:
+
+$$\begin{aligned}
+    f\left(x\right)&=Q\left(x\right)g\left(x\right)+R\left(x\right)\\
+    \operatorname{deg}{Q}&=\operatorname{deg}{f}-\operatorname{deg}{g}\\
+    \operatorname{deg}{R}&<\operatorname{deg}{g}
+\end{aligned}$$
+
+&emsp;&emsp;我们称 $Q\left(x\right)$ 为 $g\left(x\right)$ 除 $f\left(x\right)$ 的**商(Quotient)**,$R\left(x\right)$ 为 $g\left(x\right)$ 除 $f\left(x\right)$ 的**余数(Remainder)**.
+
+&emsp;&emsp;亦可记作
+
+$$f\left(x\right)\equiv R\left(x\right)\pmod{g\left(x\right)}$$
+
+## <span id="ln-exp">多项式的对数函数与指数函数</span>
+
+&emsp;&emsp;对于一个多项式 $f\left(x\right)$,可以将其对数函数看作其与麦克劳林级数的复合:
+
+$$\ln{\left(1-f\left(x\right)\right)}=-\sum_{i=1}^{+\infty}\frac{f^{i}\left(x\right)}{i}$$
+
+&emsp;&emsp;其指数函数同样可以这样定义:
+
+$$\exp{f\left(x\right)}=e^{f\left(x\right)}=\sum_{i=0}^{+\infty}\frac{f^{i}\left(x\right)}{i!}$$
+
+## <span id="multipoint-eval-interpolation">多项式的多点求值和插值</span>
+
+&emsp;&emsp;**多项式的多点求值(Multi-point evaluation)** 即给出一个多项式 $f\left(x\right)$ 和 $n$ 个点 $x_{1},x_{2},...,x_{n}$,求
+
+$$f\left(x_{1}\right),f\left(x_{2}\right),...,f\left(x_{n}\right)$$
+
+&emsp;&emsp;**多项式的插值(Interpolation)** 即给出 $n+1$ 个点
+
+$$\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),...,\left(x_{n},y_{n}\right)$$
+
+&emsp;&emsp;求一个 $n$ 次多项式 $f\left(x\right)$ 使得这 $n+1$ 个点都在 $f\left(x\right)$ 上.
+
+&emsp;&emsp;这两种操作的实质就是将多项式在**系数表示**和**点值表示**间转化.
+
+# References
+
+&emsp;&emsp;[**Picks's Blog**](https://picks.logdown.com)
+
+&emsp;&emsp;[**Miskcoo's Space**](https://blog.miskcoo.com)
 
-- 
2.11.0