From a485cdc1eb14bff977bcaa0e525d387414a94485 Mon Sep 17 00:00:00 2001 From: Tri-solaris Date: Fri, 1 Mar 2019 22:53:57 +0800 Subject: [PATCH] feat: Update poly.md --- 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 -------------- mkdocs.yml | 8 +- 7 files changed, 1 insertion(+), 624 deletions(-) delete mode 100755 docs/math/poly-div-mod.md delete mode 100755 docs/math/poly-inv.md delete mode 100755 docs/math/poly-ln-exp.md delete mode 100644 docs/math/poly-multipoint-eval-interpolation.md delete mode 100644 docs/math/poly-newton.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 deleted file mode 100755 index 64f537bc..00000000 --- a/docs/math/poly-div-mod.md +++ /dev/null @@ -1,130 +0,0 @@ -# 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[多项式求逆](../poly-inv) - -  设给定函数为 $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}}$$ - -  应用 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}$$ - -  时间复杂度 - -$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$ - -## [多项式开方](../poly-sqrt) - -  设给定函数为 $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}}$$ - -  应用 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}$$ - -  时间复杂度 - -$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)$$ - -## [多项式 exp](../poly-exp) - -  设给定函数为 $h\left(x\right)$,有方程: - -$$g\left(f\left(x\right)\right)=\ln{f\left(x\right)}-h\left(x\right)\pmod{x^{n}}$$ - -  应用 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}$$ - -  时间复杂度 - -$$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 deleted file mode 100755 index 4800f2dc..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>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 38939974..48bd216a 100644 --- a/mkdocs.yml +++ b/mkdocs.yml @@ -121,13 +121,7 @@ nav: - 拉格朗日插值: math/lagrange-poly.md - 快速傅里叶变换: math/fft.md - 快速数论变换: math/ntt.md - - 快速沃尔什变换: math/fwt.md - - 多项式求逆: math/poly-inv.md - - 多项式开方: math/poly-sqrt.md - - 多项式除法|取模: math/poly-div-mod.md - - 多项式对数函数|指数函数: math/poly-ln-exp.md - - 多项式牛顿迭代: math/poly-newton.md - - 多项式多点求值|快速插值: math/poly-multipoint-eval-interpolation.md + - 快速沃尔什变换: math/fwt.mdg - 组合数学: - 排列组合: math/combination.md - 卡特兰数: math/catalan.md -- 2.11.0