快速傅里叶变换
对于一个多项式 $ F(x) = \sum \limits_{i=0}^{n} a_i x^i $，若有 $ n + 1 $ 组数列 $ { (x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n) } $。满足 $ \forall i \in [0, n], y_i = F(x_i) $ 且 $ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n [x_i = x_j] = 0 $，那么就能确定唯一的 $ {a_i} $，叫做点值表示法。
对于 $ x^n = 1 $ 的解有 $ n $ 个，记 $ {\omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1}} $，满足 \(\omega_n^i = {(\omega_n^1)}^i\)。且 $ \omega_n^i $ 均在单位圆上，那么就有 $ \omega_n^k = \cos k {2\pi \over n} + i \sin k {2 \pi \over n} $。
若 $ n \in {2^k | k \in \mathbb{N+}} $。那么 $ \omega_n^k = -\omega_n^{k+{n\over2}} $，直接代入即可证明。
快速傅里叶变换(DFT)
对于两个多项式 $ F(x), G(x) $，珂以将 $ F(x), G(x) $ 转换成点值表示法，然后对相同的 $ x $，将 $ F(x), G(x) $ 相乘即可。设 $ F(x), G(x) $ 的项数分别为 $ a, b $，令 $ n = 2 \times \text{highbit}(a + b - 1) $。这里取 $ x $ 为 $ \omega_n^k $，那么 $ x^a $ 就是 $ \omega_n^{ak} $。令 $ F(x) = \sum \limits_{i=0}^{n - 1} a_i x^i, F_1(x) = \sum \limits_{i=0}^{{n \over 2} - 1} a_{2i} x^{2i}, F_2(x) = \sum \limits_{i=0}^{{n \over 2} - 1} a_{2i+1} x^{2i+1} $。那么显然有
\[F(\omega_n^k) = F_1(\omega_n^{2k}) + \omega_n^k F_2(\omega_n^{2k}) \\ = F_1(\omega_{n \over 2}^k) + \omega_n^k F_2(\omega_{n \over 2}^k) \\ F(\omega_n^{k+{n \over 2}}) = F_1(\omega_n^{2k+n}) + \omega_n^{k + {n \over 2}} F_2(\omega_n^{2k+n}) \\ = F_1(\omega_{n \over 2}^k) - \omega_n^k F_2(\omega_{n \over 2}^k) \\ (k < {n \over 2}) \]那么只需要求出 $ F_1, F_2 $，就能在 $ \Theta(n) $ 的时间求出 $ F(\omega_n^k) $。然后注意到 $ {n \over 2} \in {2^k,k\in\mathbb{N+}} $，于是珂以递归求解。总共 $ \log n $ 层，每层时间 $ \Theta(n) $，总时间 $ \Theta(n \log n) $。
快速傅里叶逆变换(IDFT)
现在已经得到的 $ {(\omega_n^0, y_0), (\omega_n^1, y_1), \cdots, (\omega_n^{n - 1}, y_{n - 1})} $ 满足 $ \forall y_i = (F * G)(\omega_n^i) $。需要求出系数。不妨令 $ H = F * G, H(x) = \sum \limits_{i=0}^{n - 1} a_i x^i $。设有多项式 $ D(x) = \sum \limits_{i=0}^{n-1} y_i x^i $，和数列 $ {c_0, c_1, \cdots, c_{n - 1}} $，满足 $ c_k = D(\omega_n^{-k}) = \sum \limits_{i=0}^{n - 1} y_i {(\omega_n{-k})}i $。
\[\sum \limits_{i=0}^{n - 1} y_i {(\omega_n^{-k})}^i = \sum \limits_{i=0}^{n-1} {(\omega_n^{-k})}^i \sum \limits_{j=0}^{n-1} a_j {(\omega_n^j)}^i = \sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} a_j {(\omega_n^{j-k})}^i \\ = \sum \limits_{i=0}^{n-1} a_i \sum \limits_{j=0}^{n-1} {(\omega_n^{i-k})}^j \]设 $ P(x) = \sum \limits_{i=0}^{n-1} x^i $。
- $ k \ne 0 $，那么有 $ xP(x) - P(x) = x^n - 1\ \Rightarrow\ P(x) = {x^n - 1 \over x - 1} $。代入 $ \omega_n^k $ 得 $ {\omega_n^{kn} - 1 \over \omega _n^k - 1} $。所以 $ P(x) = 0 $。
- $ k = 0 $，此时柿子的值显然为 $ n $。
所以 $ P(\omega_n^k) = [k = 0] \times n $。于是原式 $ = \sum \limits_{i=0}^{n-1} a_i P(\omega_n^{i-k}) = a_k n $。所以 $ a_i = {c_i \over n} $。
对 $ D(x) $ 跑快速傅里叶变换，得 $ {(\omega_n^0, d_0), (\omega_n^1, d_1), \cdots, (w_n^{n-1}, d_{n-1})} $，那么 $ a_i = {d_{(n-i) \mod n} \over n} $。
也可以将所有 $ \omega_n^1 $ 改成 $ \omega_n^{-1} $ 即可。
快速数论变换
\(\delta_p(a)\) 为 \(a^n \equiv 1\ (\text{mod}\ p)\) 最小的 $ n $。
若 $ a^n \equiv 1\ (\text{mod}\ p) $，则 $ \delta_p(a)\ |\ n $。证明:
令 $ n = q\delta_p(a) + r \(，\) 0 \le r < \delta_p(a) $ 且 $ q, r \in \mathbb{N}^+ \cup {0} \(。\) a^r \equiv a^r \times a^{q \delta_p(a)} \equiv a^n \equiv 1\ (\text{mod}\ p) $。因为 $ r < \delta_p(a) $，于定义矛盾，不成立。所以 $ r = 0 $，即 $ \delta_p(a)\ |\ n $。
若 $ a $ 是模 $ p $ 的一个原根，当且仅当 $ \delta_p(a) = \varphi(p) $。
令 $ g $ 为模 $ p $ 的一个原根，$ p $ 是质数，那么满足 $ \omega_n^1 \equiv g^{p-1 \over n}\ (\text{mod}\ p) $。证明:
$ \omega_n^1 = \sqrt[n]1 = 1^{1 \over n} $，所以若 $ \omega_n^1 \equiv g^{p-1 \over n}\ (\text{mod}\ p) $ 成立，只需证明 $ g^{p - 1} \equiv 1\ (\text{mod}\ p) $，由前置证明的性质得原恒等式等价于 $ \delta_p(g)\ |\ (p - 1) $，由定义可转化 $ \varphi(p)\ |\ (p - 1) $，由 $ \varphi $ 的定义得 $ \varphi(p) = p \times \prod \limits_{i=1}^{k} {p_i - 1 \over p_i} = p - 1 $，显然 $ (p - 1)\ |\ (p - 1) $，所以命题成立。
所以直接把 FFT 中的 $ \omega_n^1 $ 替换成 $ g^{p - 1 \over n} $ 即可。通常为了方便计算，模数 $ p $ 的选取通常满足 $ n\ |\ (p - 1) $。一般选 $ p = 998244353 = 7 \times 17 \times 2^{23} + 1, g = 3 $。
优化
递归从上往下分配常数灰常大，考虑从小往上递推。那么只要求出最后一层的即可。最后一层的二进制下标显然是倒着标的，例如 000 100 010 110 001 101 011 111。证明:
考虑归纳法，对于第 $ k $ 层（指 \(2^k\) 个点），那么在二进制中第 $ k $ 位，左边 $ 2^{k - 1} $ 个点是 0，右边 $ 2^{k - 1} $ 个点是 1。那么若第 $ k - 1 $ 的两边满足下标二进制倒着标，就满足第 $ k $ 层下标倒着标。对于边界 $ k = 0 $ 的情况，显然是满足的。证完了。
那么维护 $ u $ 表示当前的序列下标即可。
快速沃尔什变换
快速沃尔什变换(FWT)，用于计算二进制操作卷积。好像也有说叫快速莫比乌斯变换(FMT)的。
OR
令序列为 $ a, b $，卷积得到序列为 $ c $。
与快速傅里叶变换同样思路，求出 $ FWT_{a,i} = \sum \limits_{j\ \text{or}\ i=i} a_j $，证明一下正确性。
\[FWT_{a,i} \times FWT_{b,i} = (\sum \limits_{j\ \text{or}\ i = i} a_j) (\sum \limits_{k\ \text{or}\ i = i} b_k) = \sum \limits_{j\ \text{or}\ i = i} \sum \limits_{k\ \text{or}\ i = i} a_j b_k \\ = \sum \limits_{(j\ \text{or}\ k)\ \text{or}\ i = i} a_j b_k = FWT_{c,i} \\ \]$ a \rightarrow FWT_{a} $
对于 $ [1,n] $ 的 $ FWT $，考虑依据第一位分治，令第一位为 $ 0 $ 的（前 $ n \over 2 $ 个点）$ FWT_1 $，为 $ 1 $ 的 $ FWT_2 $。那么 $ FWT = \text{merge}(FWT_1, FWT_1 + FWT_2) $。
$ FWT_{a} \rightarrow a $
直接逆运算，$ a = \text{merge}(a_1, a_2 - a_1) $。
AND
同理可得。
XOR
定义 $ a \oplus b = \text{popcount}(a\ \text{AND}\ b)\ \text{mod}\ 2 $，设 $ FWT_{a, i} = \sum \limits_{j\oplus i=0} a_j - \sum \limits_{j\oplus i=1} a_j $。正确性:
\[FWT_{a,i} \times FWT_{b,i} = (\sum \limits_{j \oplus i = 0} a_j - \sum \limits_{j \oplus i = 1} a_j) (\sum \limits_{k \oplus i = 0} b_k - \sum \limits_{k \oplus i = 1} b_k) \\ \sum \limits_{j \oplus i = 0} \sum \limits_{k \oplus i = 0} a_j b_k + \sum \limits_{j \oplus i = 1} \sum \limits_{k \oplus i = 1} a_j b_k - \sum \limits_{j \oplus i = 1} \sum \limits_{k \oplus i = 0} a_j b_k - \sum \limits_{j \oplus i = 1} \sum \limits_{k \oplus i = 0} a_j b_k \\ \because (i \oplus j)\ \text{XOR}\ (i \oplus k) = i \oplus (j\ \text{XOR}\ k), \therefore \\ = \sum \limits_{i \oplus (j\ \text{XOR}\ k) = 0} a_j b_k - \sum \limits_{i \oplus (j\ \text{XOR}\ k) = 1} a_j b_k = FWT_{c,i} \\ \]\[FWT = \text{merge}(FWT_1 + FWT_2, FWT_1 - FWT_2) \\ a = \text{merge}({a_1 + a_2 \over 2}, {a_1 - a_2 \over 2}) \]多项式求逆
令 $ f_0^{-1}(x) * f(x) \equiv 1\ (\text{mod}\ x^{\lceil{n \over 2}\rceil}) $。则
\[f(x) * f_0^{-1}(x) \equiv 1\ (\text{mod}\ x^{\lceil{n \over 2}\rceil}) \\ f(x) * f^{-1}(x) \equiv 1\ (\text{mod}\ x^{\lceil{n \over 2}\rceil}) \\ \]所以 $ f_{0}^{-1} - f^{-1} \equiv 0\ (\text{mod}\ x^{\lceil{n \over 2}\rceil}) $，两边平方 $ f_{0}^{-2} + f^{-2} - 2f_0^{-1} f^{-1} \equiv 0\ (\text{mod}\ x^n) $，同乘 $ f(x) $ 并移项的 $ f^{-1}(x) = 2f_0^{-1}(x) - f(x)f_0^{-2} $。
多项式除法
对于一个次数为 $ n $ 的多项式 $ A(x) \(，\) x^nA({1 \over x}) $ 即是 $ A(x) $ 反转系数得到的多项式。那么有
\[x^nA({1 \over x}) = x^m B({1 \over x}) x^{n-m} Q({1 \over x}) + x^{n-m+1} x^{m-1} Q({1 \over x}) \\ A^R(x) = B^R(x) Q^R(x) + x^{n-m+1} Q({1 \over x}) \\ A^R(x) \equiv B^R(x) Q^R(x)\ (\text{mod}\ x^{n - m + 1}) \\ Q^R(x) = A^R(x) * {B^R}^{-1}(x)\ (\text{mod}\ x^{n - m + 1}) \\ \]多项式逆元即可。
多项式牛顿迭代
给定函数 \(g(x)\)，且有 \(g(f(x))\equiv 0(\text{mod}\ x^n)\)。求 \(f(x)\) 在模 \(x^n\) 意义下的各项系数。
考虑倍增，从满足 \(g(f_0(x)) \equiv 0(\text{mod}\ x^{\lceil {n \over 2} \rceil})\)，的 \(f_0(x)\) 推广到 \(f(x)\)。
将 \(g(f(x))\) 在 \(f_0(x)\) 处泰勒展开得到: \(\sum \limits_{i=0}^{\infty} {{d^i g \over dx^i}(f_0(x)) \over i!} (f(x) - f_0(x))^i \equiv 0 (\text{mod}\ x^n)\)。
注意到 \(f(x) - f_0(x)\) 最低项是 \(\lceil{n \over 2}\rceil\) 的，那么就有 \(g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) \equiv 0(\text{mod}\ x^n)\)。
移项得到: \(f(x) \equiv f_0(x) - {g(f_0(x)) \over g'(f_0(x))} (\text{mod}\ x^n)\)。
多项式 ln, exp
ln
链式法则: \((g \circ f)'(x) = g'(f(x)) \times f'(x)\)（注意 \('\) 的位置，即求导对象）
对数函数求导: \(\ln' x = {1 \over x}\)。
那么 \(g=\ln,f=A, h(x) = \ln f(x)\)，代入就有 \(h'(x) = {f'(x) \over f(x)}\)。
\(h'(x)\) 珂以 \(\Theta(n \log n)\) 求出，然后求个不定积分就好了。
exp
使用牛顿迭代，据题有 \(\ln f(x) - h(x) \equiv 0(\text{mod}\ n)\)，得到: \(f(x) \equiv f_0(x) - {\ln f_0(x) - h(x) \over {1 \over f_0(x)}}(\text{mod}\ x^n)\ \Rightarrow\ f(x) \equiv f_0(x)(1-\ln f_0(x) + h(x))(\text{mod}\ x^n)\)。
直接递推计算即可，时间 \(\Theta(n \log n)\)。
常系数齐次线性递推
令 $ F(\sum \limits_{i=1}^{n} c_i x^i) = \sum \limits_{i=1}^{n} c_i f(i) $，很显然有 $ F(a + b) = F(a) + F(b) $
构造多项式 $ G(x) = x^k - \sum \limits_{i=0}^{k-1} c_i x^i = 0 $，那么显然 $ F(A(x) + G(x)) = F(A(x)) $。
所以答案就是 $ F(x^n) = F(x^n\ \text{mod}\ G(x)) $，因为 $ G(x) $ 的最高次数 $ k $，所以 $ x^n\ \text{mod}\ G(x) $ 的次数是 $ k - 1 $，又因为 $ f_{0, \cdots, k - 1} $ 已经给出，所以就可以算了。
然后考虑计算 \(x^n\ \text{mod}\ G(x)\)，采用快速幂思想，时间复杂度 \(\Theta(k \log k \log n)\)。
标签：limits,text,sum,poly,omega,over,mod From： https://www.cnblogs.com/xieruyu666/p/18382568