FFT/NTT

前置知识多项式除法|取模该部分见 多项式操作 特征值与特征向量（这部分我也不怎么理解，就大概记个结论） 对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $\lambda$ 满足$$A\vec v = \lambda\vec v$$移项则有 $(\lambda I - A)\vec v = 0$，其中 $I$ 为单位矩阵 那么有解的充要条件是 $det(\lambda I - A) = 0$ 令 $f(\lambda) = det(\lambda I - A)$，即此时可将 $det (\lambda I - A)$ 看作一个 $n$ 阶多项式，则称 $f(\lambda)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$，其任意特征值 $\lambda_0$ 都满足 $f(\lambda_0) = 0$ $\text{Hamiton-Cayley}$定理对矩阵 $A$ 及其特征多项式 $f(x)$，满足 $f(A) = O$，其中 $O$ 为零矩阵 证明留坑 常系数齐次线性递推求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即$$h_n = ...

首先定义多项式的度数 $degA$ 为多项式 $A(x)$ 的最高次数 那么多项式 $A(x)$ 的逆即为存在多项式 $B(x)$ 使得条件满足：$$A(x)B(x) \equiv 1 \pmod{x^n}$$ 求解过程分治 $FFT$对 $A(x) = \sum\limits_{k = 0}^{n - 1} a_kx^k, B(x) = \sum\limits_{k = 0}^{n - 1} b_kx^k$ 从常数项考虑，有 $b_0 = \frac1{a_0}$，则由 $\sum\limits_{k = 0}^n b_ka_{n - k} = 0$ 可得$$b_k = \sum\limits_{i = 0}^{k - 1} b_i\left(- \frac{a_{k - i}}{a_0}\right)$$ 倍增迭代假设存在多项式 $A(x)$ ，以及其逆 $B(x)$ 满足条件 ，那么必定有$A(x)B(x) \equiv 1 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (1)$ ，因为 $x^n$ 是 $x^{\left\l ...

多项式求逆该部分见 多项式求逆 多项式除法|取模有 $F(x) = G(x)Q(x) + R(x)$，给定 $F(x)$ 与 $G(x)$，求解 $Q(x), R(x)$，其中 $F(x), G(x)$ 最高次数分别为 $n, m$ 显然地，$Q(x), R(x)$ 的最高次数必定不超过 $n - m, m - 1$，考虑式子变形$$\begin{aligned}&F(x) = G(x)Q(x) + R(x) \\\Rightarrow &F(\frac1x) = G(\frac1x)Q(\frac1x) + R(\frac1x) \\\Rightarrow &x^nF(\frac1x) = x^mG(\frac1x)x^{n - m}Q(\frac1x) + x^{n - m + 1}x^{m - 1}R(\frac1x) \\\end{aligned}$$令 $A_R(x)$ 表示 $A(x)$ 系数翻转后得到的多项式，即 $A(x)$ 系数 $(a_0, a_1, …, a_n)$，$A_R(x)$ 系数 $(a_n, a_{n - 1}, …, a_1) ...

概念引入阶对于$p \in N_+$且$(a, p) = 1$，满足$a^r \equiv 1 (mod p)$的最小的非负$r$为$a$模$p$意义下的阶，记作$\delta_p(a)$ 原根定义：若$p \in N_+$且$a \in N$，若$\delta_p(a) = \phi(p)$，则称$a$为模$p$的一个原根相关定理： 若一个数$m$拥有原根，那么它必定为$2, 4, p^t, 2p^t (p$为奇质数$)$的其中一个 每个数$p$都有$\phi(\phi(p))$个原根 　　证明：若$p \in N_+$且$(a, p) = 1$，正整数$r$满足$a^r \equiv 1 (mod p)$，那么$\delta(p) | r$，由此推广，可知$\delta(p) | \phi(p)$，所以$p$的原根个数即为$p$之前与$\phi(p)$互质的数，即$\phi(p)$故定理成立 　　　　　　- 若$g$是$m$的一个原根，则$g, g^1, g^2, …, g^{\phi(m)} (mod p)$两两不同 　　　　原根求法： ...

概念引入　　- 点值表示　　　　对于一个$n - 1$次多项式$A(x)$，可以通过确定$n$个点与值（即$x$和$y$）来表示这唯一的$A(x)$ 　　- 复数　　　　对于一元二次方程　　　　$$x^2 + 1 = 0$$　　　　在实数范围内无解，那么我们将实数范围扩充，就得到了复数，再令$i$为该方程的解，即　　　　$$i^2 = - 1$$　　　　那么就定义$z = a + bi$的数为复数，则有　　　　当$b = 0$时，$z$为实数　　　　当$b \neq 0$时，$z$为虚数　　　　当$a = 0 \&\& b \neq 0$时，$z$为纯虚数　　　　其中，复数满足加法交换律、结合律、乘法分配率等 　　　　复数相乘：$z_1 = a_1 + b_1i, z_2 = a_2 + b_2i$，则$z_1 × z_2 = (a_1 + b_1i)(a_2 + b_2i) = (a_1a_2 - b_1b_2) + (a_1b_2 + b_1a_2)i$，它们相乘还是一个复数，在复平面上理解，就是模长相乘，幅角相加 　　　　共轭复数：当两个复数实部相同，虚部为 ...