From a40df37f6c62ea387465940d304e24560b58ea1b Mon Sep 17 00:00:00 2001
From: Tri-solaris <trisolaris@126.com>
Date: Fri, 1 Mar 2019 23:24:18 +0800
Subject: [PATCH] Update poly-div-mod.md

---
 docs/math/poly-div-mod.md | 130 ++++++++++++++++++++++++++++++++++++++++++++++
 docs/math/poly-sqrt.md    |  78 ----------------------------
 mkdocs.yml                |   2 +-
 3 files changed, 131 insertions(+), 79 deletions(-)
 create mode 100755 docs/math/poly-div-mod.md
 delete 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..d5e88dc9
--- /dev/null
+++ b/docs/math/poly-div-mod.md
@@ -0,0 +1,130 @@
+# Description
+
+给定多项式 $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
+
+发现若能消除 $R\left(x\right)$ 的影响则可直接[**多项式求逆**](../poly-inv)解决.
+
+考虑构造变换
+
+$$f^{R}\left(x\right)=x^{\operatorname{deg}{f}}f\left(\frac{1}{x}\right)$$
+
+观察可知其实质为反转 $f\left(x\right)$ 的系数.
+
+设 $n=\operatorname{deg}{f},m=\operatorname{deg}{g}$.
+
+将 $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}$$
+
+注意到上式中 $R^{R}\left(x\right)$ 的系数为 $x^{n-m+1}$,则将其放到模 $x^{n-m+1}$ 意义下即可消除 $R^{R}\left(x\right)$ 带来的影响.
+
+又因 $Q^{R}\left(x\right)$ 的次数为 $\left(n-m\right)<\left(n-m+1\right)$,故 $Q^{R}\left(x\right)$ 不会受到影响.
+
+则:
+
+$$f^{R}\left(x\right)\equiv Q^{R}\left(x\right)g^{R}\left(x\right)\pmod{x^{n-m+1}}$$
+
+使用多项式求逆即可求出 $Q\left(x\right)$,将其反代即可得到 $R\left(x\right)$.
+
+时间复杂度 $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-sqrt.md b/docs/math/poly-sqrt.md
deleted file mode 100755
index 7522e408..00000000
--- a/docs/math/poly-sqrt.md
+++ /dev/null
@@ -1,78 +0,0 @@
-# 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 c74ea25c..313f8415 100644
--- a/mkdocs.yml
+++ b/mkdocs.yml
@@ -122,7 +122,7 @@ nav:
       - 快速傅里叶变换: math/fft.md
       - 快速数论变换: math/ntt.md
       - 快速沃尔什变换: math/fwt.md
-      - 多项式开方: math/poly-sqrt.md
+      - 多项式除法|取模: math/poly-div-mod.md
     - 组合数学:
       - 排列组合: math/combination.md
       - 卡特兰数: math/catalan.md
-- 
2.11.0