标签：limits text sum poly omega over mod

板子

快速傅里叶变换

对于一个多项式 $ 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^{-ik})} $。

\[\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 $ 表示当前的序列下标即可。

任意模数 NTT

三模NTT

实战中值域通常为 $n \times \text{mod}^2 = 10^{24}$。珂以选取选取三个模数，使得三个模数的积大于 $10^{24}$，珂以选取

\[469762049=7 \times 2^{25} + 1, g=3 \\ 998244353 = 119 \times 2^{23} + 1, g=3 \\ 1004535809=479 \times 2^{21}+1, g=3 \\ \]

分别做一次 NTT，得到 $x_1, x_2, x_3$，即 $\begin{cases} x_1 \equiv x\ (\text{mod}\ mod_1) \\ x_2 \equiv x\ (\text{mod}\ mod_2) \\ x_3 \equiv x\ (\text{mod}\ mod_3) \\ \end{cases}$，珂以通过CRT/EXCRT合并，先合并前两个得到 $x \equiv x_1 + mod_1({x_2 - x_1 \over mod_1}\ \text{mod}\ mod_2)\ (\text{mod}\ mod_1 mod_2)$，写成 $x \equiv x_4\ (\text{mod}\ mod_4)$，继续合并得到: $x = x_4 + mod_4 ({x_3 - x_4 \over mod_4}\ \text{mod}\ mod_3)$。

五次FFT

首先注意 FFT 支持的精度，

快速沃尔什变换

快速沃尔什变换(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)$。

实践一下: 多项式开根。

根据题意有 $g(f(x))=f^2(x)-h(x)\equiv0(\text{mod}\ x^n)$。使用牛顿迭代法得 $f(x)=f_0(x) - {f_0^2(x)-h(x) \over 2f_0(x)} = {f_0(x) \over 2} + {h(x) \over 2f_0(x)}$，多项式求逆递推计算即可，时间 $\Theta(n \log 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

使用牛顿迭代，据题有 $g(f(x)) = \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)$。

多项式快速幂

显然珂以套用快速幂模板，把乘法换成多项式乘法。时间 $\Theta(n \log n \log k)$。

但是有点慢，~~我不觉得，卡这个（除了除我以外的人）就是唐诗，我说的~~，比如模板题 $k \le 10^{10^5}$，这种时候考虑对多项式取 $\ln$，然后乘 $k$ 后 $\exp$ 回去。但是注意到，过程中将 $k$ 模 $p$ 了，接下来证明正确性:

首先证明 $f(x^p) \equiv f(x)^p(\text{mod}\ p)$：

归纳法证明，设 $f(x)$ 度数为 $n$，令 $f_0(x) = f(x)\ \text{mod}\ x^n$（即去掉次数为 $n$ 的项），$a={f(x) - f_0(x) \over x^n}$。那么有 $f_0(x^p) = f_0(x^p)$，$f(x)^p \equiv(f_0(x) + axⁿ⁾p $。欧拉降幂一下: $(a + b)^p \equiv (a+b)^{p\ \text{mod}\ \varphi(p)} \equiv a+b(\text{mod}\ p)$，又因为 $a^p=a^{p\ \text{mod}\ \varphi(p)} = a$，所以 $(a+b)^p\equiv a^p+b^p(\text{mod}\ p)$。

$(f_0(x) + ax^n)^p \equiv f_0^p(x) + ax^{pn} \equiv f_0(x^p) + ax^{pn} \equiv f(x^p)\ (\text{mod}\ p)$。

证明完了就好办了，实战中通常 $n < p$，那么 $f(x^p) \equiv [x^0]f(x)(\text{mod}\ x^n)$。

那么 $f^{k-p}(x)={f^k(x) \over [x^0] f(x)}$，因为本题 $a_0=1$，因此珂以直接取模。否则 $f^k(x) = f^{k\ \text{mod}\ p}(x) \times ([x^0] f(x))^{\lfloor {k \over p} \rfloor}$。

但是注意到加强版若要求 $f^{k\ \text{mod}\ p}$ 需要龟速幂，所以考虑优化。

显然的思路，珂以找到最小的 $t$ 满足 $[x^t]f(x) \ne 0$，令其为 $v$。那么有 $f^k(x) = {({f(x) \over vx^t})}^k \times v^kx^{kt}$。

多项式平移

已知多项式 $F(x) = \sum \limits_{i=0}^{n} a_i x^i$，求 $F(x+c)$。将 $F(x)$ 在 $c$ 处泰勒展开，得到 $F(x) = \sum \limits_{i=0}^{n} {F^{(i)}(c) \over i!} {(x-c)}^i$。代入可得 $F(x+c) = \sum \limits_{i=0}^{n} {F^{(i)}(c) \over i!} x^i = \sum \limits_{i=0}^{n} {x^i \over i!} $。

多项式多点求值

构造多项式 $G_0(x) = \prod \limits_{i=1}^{\lfloor {n \over 2} \rfloor} (x - x_i), G_1(x) = \prod \limits_{i=\lfloor {n \over 2} \rfloor + 1}^n (x - x_i) $。那么容易注意到 $\forall i \in [1, \lfloor {n \over 2} \rfloor]\ G_0(x_i) = 0$，$G_1$ 同理。那么令 $F_0(x) = F(x)\ \text{mod}\ G_0(x)$，显然 $\forall i \in [1, \lfloor {n \over 2} \rfloor], F_0(x) = F(x)$，而且注意到 $F_0(x)$ 的项数是严格小于 $\lfloor {n \over 2} \rfloor$ 的，于是分治即可。时间 $\Theta(n \log^2 n)$。

分治FFT

顾名思义，分治计算贡献，对于 $[l,r]$ 的区间，先计算 $[l,mid]$ 的值，再计算 $[l,mid]$ 对 $(mid,r]$ 的贡献，然后计算 $(mid, r]$。那么将 $f_{[l,mid]}$ 与 $g_{[1,r-l]}$ 卷积后将超过 $mid$ 的项加到 $f_{(mid,r]}$ 上即可。

时间 $\Theta(n \log^2 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)$。

PolandBall and Many Other Balls

倍增FFT模板。

设 $f_{n,k}$ 为从 $n$ 个球中取出 $k$ 组的方案数，那么显然有 $f_{n,k} = f_{n-1,k}+f_{n-1,k-1}+f_{n-2,k-1}$，不太好优化。于是考虑 $f_{n,k}$ 如何转移到 $f_{2n,k}$。那么有 $f_{2n,k} = \sum \limits_{i=0}^{k} f_{n,i} \times f_{n,k-i} + \sum \limits_{i=0}^{k-1} f_{n-1,i} \times f_{n-1,k-i-1}$。那么考虑倍增，设 $F_n(x) = \sum \limits_{i=0}^{k} f_{x,i} x^i$，那么显然有:

\[\begin{cases} \text{F}_{2n-2}(x) = \text{F}^2_{n-1}(x) + x\text{F}_{n-2}^2 (x) \\ \text{F}_{2n-1}(x) = \text{F}_n (x) \text{F}_{n-1}(x) + x \text{F}_{n-1}(x) \text{F}_{n-2}(x) \\ \text{F}_{2n}(x) = \text{next}(\text{F}_{2n-1}, \text{F}_{2n-2}) \\ \end{cases} \]

维护 $\text{F}_{n-2}, \text{F}_{n-1}, \text{F}_{n}$ 即可，时间 $\Theta(k \log k \log n)$。

标签：limits,text,sum,poly,omega,over,mod
From： https://www.cnblogs.com/shengxuanyi/p/18414761

poly

板子