Polynomial Techniques(TBD)
Polynomial Techniques
多项式技术。
本来叫做多项式理论的，但仔细审视发现并没有太多值得被称作理论的东西：全都是多项式环内的计算技术。
算了。本来就是为计数理论生成函数服务的技术。由更深的视点再写多项式理论吧。
Polynomial
定义：多项式域。加减乘除求导积分。
Fourier Transform
系数表示。代数基本定理。点值表示。
单位根。消去引理。折半引理。
变换矩阵。范德蒙德矩阵。逆矩阵。
Number Theory Transform
使用原根。
Convolution
多项式乘法的卷积表示。
Inverse of a Polynomial
多项式 $ (AB \equiv 1)(x) \pmod{x^n} $ ，知 $ A $ 求 $ B $.
考虑倍增。易有 $ B_1 \equiv ([x^0]A)^{-1} \pmod {x^1} $.
我们已经有 $ AB_n-1 \equiv 0 \pmod {x^n} $ ，接下来
$$ \begin{aligned} (AB_n-1)^2 \equiv 0\pmod{x^{2n}} \\ A^2B_n^2-2AB_n+1\equiv 0 \pmod {x^{2n}} \\ B_{2n}(A^2B_n^2-2AB_n+1)\equiv 0 \pmod {x^{2n}} \\ B_{2n} \equiv 2B_n-AB_n^2 \pmod {x^{2n}} \end{aligned} $$
这样我们就求出了一个多项式的逆元。
复杂度是 $ T(n)=T({n\over2})+\mathcal O(n\log n)=\mathcal O(n\log n) $.
Bernoulli Number
求第 $ n $ 项 Bernoulli number.
Sol. Bernoulli number 的 egf 为 $ \hat{B}(x)={x\over e^x-1}=\sum B_i{x^i\over i!} $.
将 $ e^x $ 展开，
$$ \hat{B}={1\over \sum_{i=0}^ \infty{x_i\over (i+1)!}} $$
保留前 $ n $ 项即可。
Tsinsen A1493
$ n $ 点无向连通图计数。
Sol. 令 $ f_n $ 表示题目所求，容易写出式子
$$ \begin{align} f_n&=2^{n\choose2}-\sum_i {n-1\choose i-1}f_i2^{n-i\choose 2} \\ 2^{n\choose 2}&=\sum_i{n-i\choose i-1} f_i 2^{n-i\choose 2} \\ &=\sum_i {(n-1)!\over(i-1)!(n-i)!}f_i2^{n-i\choose2}\\ {2^{n\choose2}\over(n-1)!}&=\sum_i {f_i\over (i-1)!} {2^{n-i\choose i}\over (n-i)!} \end{align} $$
令 $ A(x)=\sum{2^{n\choose2}\over{(n-1)!}}x^n, B(x) = \sum {f_n\over(n-1)!}x^n, C(x) = \sum{ 2^{n \choose 2} \over n!} x^n $ ，则 $ A=BC $.
答案即为 $ [x^n]B=[x^n](AC^{-1}) $.
Division with Remainder of a Polynomial
多项式 $ (A\equiv BD+R)(x)\pmod{x^n} $ ，知 $ A,B $ 求 $ D,R $ .
我们考虑将多项式系数全部反过来，即高位到低位，低位到高位，记为 $ F^R $ .
为了研究于原来多项式的关系，我们需要将之表示回去，易发现 $ F^R(x) = x^{\deg F}F({1\over x}) $ .
那么我们有
$$ \begin{align} x^{\deg A}(A&= BD+R)({1\over x}) \\ A^R &= B^RD^R+x^{\deg A-\deg B+1}R^R \end{align} $$
注意到 $ \deg D^R < \deg A-\deg B+1 $ , 所以我们可以整个式模掉这么多次幂，求出 $ D^R=A^R(B^R)^{-1} $ ，反代回原式求出 $ D,R $ 即可。
多点求值
给 $ F $ , 求在 $ A=\{a_i\}_{i=0}^m $ 处的值。
Sol. 构造
$$ M_0(x)=\prod_{i=0}^{\lfloor{m\over2}\rfloor} (x-a_i) \\ M_1(x)=\prod_{i=\lfloor{m\over2}\rfloor}(x-a_i) $$
令
$$ Q_0 = F \mod {M_0} \\ Q_1=F\mod {M_1} $$
因为 $ M_k $ 已经包含了 $ x-a_i $ ，所以商式必然为零，显然有 $ F(a_i)=Q_0(a_i),0\le i\le \lfloor{m\over2}\rfloor; F(a_i)=Q_1(a_i),\lfloor{m\over2}\rfloor<i\le m $.
分治。总的复杂度为 $ \mathcal O(n \log^2 n) $.
常系数线性递推
（坑）
多项式 Euclid 算法
给 $ A,B $ 求最大公因式。
Sol. Euclid 算法仍然可以用到多项式环上。每次只能最高次数降低 $ 1 $ ，总的复杂度为 $ O(n^2\log n) $.
多项式模多项式
给 $ A,M $ 求 $ A^{-1}:AA^{-1}\equiv1\pmod M $.
Sol. 拓展 Euclid 自然成立。$ AP+MQ=\gcd(A,M)=1 $.
Square Root of a Polynomial
求 $ A_n:A_n^2\equiv A\pmod {x^n} $.
变形得
$$ \begin{align} (A_n^2-A)^2&\equiv0&\pmod {x^{2n}} \\ (A_n^2+A)^2&\equiv 4A_n^2A &\pmod {x^{2n}}\\ ({A_n^2+A\over2A_n})^2&\equiv A &\pmod {x^{2n}}\\ {A_n^2+A\over2A_n}&\equiv A_{2n} &\pmod {x^{2n}} \end{align} $$
复杂度同上分析为 $ \mathcal O(n\log n) $.
CF 250E
(坑)
Newton's Method of Polynomial
给 $ G $ 求 $ F:G(F(x))\equiv0\pmod {x^n} $.
仍然考虑倍增，我们设 $ G(F_t(x))\equiv0\pmod {x^{2^t}} $.
首先常数项必为 $ 0 $ 方可收敛。我们考虑模 $ x^{2^{t+1}} $ 意义，对 $ G\circ F_{t+1} $ 在 $ F_t $ 上展开，有
$$ G\circ F_{t+1}=G\circ F_t+\sum_{i>0}{G^{(i)}\circ F_t\over i!}(F_{t+1}-F_t)^i $$
注意到 $ \deg ((F_{t+1}-F_t)^2) \ge 2^{t+1} $ ，那么从第三项开始往后都为零，即有
$$ \begin{align} G\circ F_{t+1}&\equiv G\circ F_t+G'\circ F_t\times(F_{t+1}-F_t)&\pmod {x^{2^{t+1}}} \\ F_{t+1}&\equiv F_t-{G\circ F_t \over G'\circ F_t} &\pmod {x^{2^{t+1}}} \end{align} $$
多项式迭代目前没有高效算法……但结合特殊形式我们可以有很多用处。
求逆
求 $ FP\equiv 1\pmod{x^n} $.
用上式即得 $ F_{t+1} \equiv F_t-{F_tP-1\over P} \equiv F_t-F_t(F_tP-1) \pmod {x^{2^{t+1}}} $.
开方
求 $ F^2-P\equiv1\pmod {x^n} $.
用上式即得 $ F_{t+1}\equiv F_t-{F_t^2P\over 2F_t} \pmod {x^{2^{t+1}}} $.
常数项如果不是零需要用到二次剩余。
求 exp
求 $ e^P-F\equiv0\pmod {x^n} $. 变形有 $ \ln F-P\equiv0\pmod{x^n} $.
用上式即得 $ F_{t+1}\equiv F_t-(\ln F_t-P)F_t \pmod {x^{2^{t+1}}} $.
注意到 $ \ln F=\int {F'\over F} \mathrm{d}x $.
求三角函数值
求 $ \cos P-X\equiv 0 \pmod {x^n} \\ \sin P - X \equiv 0 \pmod {x^n} $.
由 Euler's Formula 有 $ e^{iF}=\cos F+i\sin F $.
直接用复数，或者模意义下用二元组代替复数。
求幂
求 $ F-P^k\equiv 0\pmod {x^n} $.
易有 $ \ln F-k\ln P\equiv0 \pmod {x^n} $.
容易发现这个方法也可以用来开方，但规避了求 $ k $ 次剩余。
Solving Differential Equation of Polynomial
已知 $ F $ , 求 $ A : {\mathrm d \over \mathrm dx} A=F(A) $ .
还是得用牛顿迭代……之所以新开一节一个是背景知识需求大了一个是式子推起来复杂了。
考虑倍增，对 $ F(A_{2n}) $ 在 $ F(A_n) $ 处展开
$$ {\mathrm d \over \mathrm dx} A_{2n} \equiv F(A_n)+F'(A_n)A_{2n}-F'(A_n)A_n \pmod {x^{2n}} $$
移项，且令 $ r:=\exp(-\int F'(A_n)\mathrm dx) $ , 两边乘 $ r $ .
$$ {\mathrm d \over \mathrm dx}A_{2n}r=r(F(A_n)-F'(A_n)A_n) $$
右式积分后除以 $ r $ 即得答案。复杂度还tm是 $ \mathcal O(n\log n) $ .
关于上式中出现的 $ r $ ，其实我们要这样考虑……
我们希望构造出来一个东西，使得上面最后那个式子成立，这样可以方便计算……
于是我们待定系数 $ r $ ，使用之前的信息可以解出它。式子化简后是
$$ {\mathrm d \over \mathrm dx} r=-rF'(A_n) $$
这是一个一阶线性其次微分方程，我们考察更一般的情况：$ {\mathrm dy\over \mathrm dx} +P(x)y=0 $ .
分离系数后的过程是机械的：
$$ \begin{align} {\mathrm dy \over y}&=-P(x)\mathrm dx \\ \ln |y|&=-\int P(x)\mathrm dx+C_1 \\ y&=Ce^{-\int P(X)\mathrm dx} \end{align} $$
其中 $ C = e^{C_1} $ .
对任意的 $ C $ 都可以的话，我们选最简单的 $ C=1 $ 即得上式。
Number Theory Transform Modulo Prime
模任意素数 FFT，只需在选取三个好的质数，分别计算，然后 CRT 合并即可。
这里有一份好的素数表。
Real Optimal
http://blog.miskcoo.com/2018/01/real-dft
使用复部的信息减少一次 FFT.
(坑)