From ce51455d79402f9b8af545deae72192b5463de58 Mon Sep 17 00:00:00 2001
From: Tri-solaris <trisolaris@126.com>
Date: Fri, 1 Mar 2019 23:22:15 +0800
Subject: [PATCH] Update poly-sqrt.md

---
 docs/math/poly-inv.md  | 75 ------------------------------------------------
 docs/math/poly-sqrt.md | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mkdocs.yml             |  2 +-
 3 files changed, 79 insertions(+), 76 deletions(-)
 delete mode 100755 docs/math/poly-inv.md
 create mode 100755 docs/math/poly-sqrt.md

diff --git a/docs/math/poly-inv.md b/docs/math/poly-inv.md
deleted file mode 100755
index 80ad1a1d..00000000
--- a/docs/math/poly-inv.md
+++ /dev/null
@@ -1,75 +0,0 @@
-# Description
-
-给定多项式 $f\left(x\right)$,求 $f^{-1}\left(x\right)$.
-
-# Methods
-
-## 倍增法
-
-首先,易知
-
-$$\left[x^{0}\right]f^{-1}\left(x\right)=\left(\left[x^{0}\right]f\left(x\right)\right)^{-1}$$
-
-假设现在已经求出了 $f\left(x\right)$ 在模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的逆元 $f^{-1}_{0}\left(x\right)$.
-有:
-
-$$\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}$$
-
-两边平方可得:
-
-$$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}}$$
-
-两边同乘 $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}}$$
-
-递归计算即可.
-
-时间复杂度
-
-$$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
-
-参见 [**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-sqrt.md b/docs/math/poly-sqrt.md
new file mode 100755
index 00000000..7522e408
--- /dev/null
+++ b/docs/math/poly-sqrt.md
@@ -0,0 +1,78 @@
+# Description
+
+给定多项式 $g\left(x\right)$,求 $f\left(x\right)$,满足:
+
+$$f^{2}\left(x\right)\equiv g\left(x\right) \pmod{x^{n}}$$
+
+# Methods
+
+## 倍增法
+
+假设现在已经求出了 $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}$$
+
+倍增计算即可.
+
+时间复杂度
+
+$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$
+
+还有一种常数较小的写法就是在倍增维护 $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
+
+参见 [**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/mkdocs.yml b/mkdocs.yml
index c07ea49b..c74ea25c 100644
--- a/mkdocs.yml
+++ b/mkdocs.yml
@@ -122,7 +122,7 @@ nav:
       - 快速傅里叶变换: math/fft.md
       - 快速数论变换: math/ntt.md
       - 快速沃尔什变换: math/fwt.md
-      - 多项式求逆: math/poly-inv.md
+      - 多项式开方: math/poly-sqrt.md
     - 组合数学:
       - 排列组合: math/combination.md
       - 卡特兰数: math/catalan.md
-- 
2.11.0