多项式半家桶

与内容无关的前置技能的前置技能之一：复数……

复数是定义在二维平面中的数。
两种表示方法：

a+bi,e^ {r+\theta i}

( $e$ 是自然对数， $i^ 2=-1$ (即虚数单位))
第一种是把 $a$ 看成 $x$ 轴座标， $b$ 看成 $y$ 轴座标。
第二种是看成一条长度为 $e^ r$ 的线段被绕着原点旋转。

用欧拉公式解释第二种表达方式：

e^ {\theta i}=\cos\theta+i\sin\theta

证明后面会讲。
两个复数相乘，相除用 $e^ {r+\theta i}$ 可以很清晰的看出是角度相加/减，长度相乘/除。

与内容无关的前置技能的前置技能之二：原根……

费马小定理：对于质数p，有 $a^ {p-1}\equiv 1(\mod p)$
p的原根是从一到p-1次幂在模p意义下都不一样的数（刚好p-1次幂模p才为1的数）。
现在有一个数a，而且 $a^ k\equiv 1(\mod p)$ (k不是 $\phi(p)$ 的倍数，那么 $a^ {gcd(k,\phi(p))}\equiv 1(\mod p)$
所以只要判断 $\phi(p)$ 除以其任何一个质因数并判断这个数作为a的幂能不能到一，能的话a就不是原根。

前置技能：快速多项式乘法(FFT&NTT)

对于两个多项式求卷积，不考虑直接相乘，而是考虑转化成点值然后相乘再插值回来。
在复数空间内画个单位圆，并从中选出 $2^k$ ( $k \in \mathbb{N}$ )个点 $p_ i$ ，使得 $p_ 0=(1,0),p_ i=p_ 1^ i,p_ 0=p_ 1^{2^ k}(1 < i < 2^ k)$
(其实就是把这个圆 $2^k$ 等分,取每个扇形逆时针方向靠前的边)
( $p_ 0=(1,0)$ 是复数空间上的乘法单位元）
现在要求这些 $p_ i$ 。
对于一个多项式 $A$ ,把它的x的奇数次的项和偶数次的项拆开,写成两个新多项式。

A(x)=a_ 0+a_ 1\times x+a_ 2\times x^ 2+\cdots

A(x)=(a_ 0+a_ 2\times x^ 2 +a_ 4 \times x^4+\cdots)+x\times (a_ 1+a_ 3\times x^ 2+a_ 5\times x^ 4+\cdots)

A(x)=A_ 0(x^2)+x\times A_ 1(x^2)

会发现 $p_ i^ 2=p_ 1^ {i\times 2}=p_ 1^ {i\times 2}\times p_ 0=p_ 1^ {2^ k+i\times 2}=p_ 1^ {(2^ {k-1}+i)\times 2}=p_ {i+2^ {k-1}}^ 2$
就是 $p_ i$ 和 $p_ i$ 绕过半圈后的那个点平方后是一样的，所以n个x时，每个子函数只有 $\frac{n}{2}$ 个 $x^2$ 的值要带进去。
然后就是递归求关于( $x^2$ )的多项式。
递归 $\log_ 2 n$ 层,每层要求的值的个数之和是 $n$ ，总复杂度 $O(n\log_ 2 n)$
求出点值乘起来之后，把结果再当做一个多项式塞回去再做FFT， $p_ i$ 取 $p_ i$ 的逆元，然后把丢出来的所有项除以 $2^ k$ 。
不知道为什么这样就完成了对特定的一列数插值的工作。

关于NTT只是使用了模意义下的单位元，逆元和原根( $a^ {\phi(p)}\equiv 1(\mod p)$ )。

前置技能：导数

就是变化量……
设 $f'(x)$ 为 $f(x)$ 的导数，那么:

f'(x)=\frac{f(x+_ \Delta x)-f(x)}{_ \Delta x}

左导数就是 $_ \Delta x$ 从负数趋近0，右导数就是 $_ \Delta x$ 从正数部分趋近0。
$f(x)$ 在某点 $x_ 0$ 存在导数必须同时满足三个条件：

$f(x)$ 在 $x_ 0$ 处有定义
$f(x)$ 在 $x_ 0$ 附近连续
$f(x)$ 的左导数和右导数相等。

对于一个函数 $f(x)$ ,下面用 $(f(x))'$ 表示它的导数。

当且仅当 $f(x)=k\times e^ x$ 时， $f(x)$ 求导是函数本身。
常用导数：

$(x^ n)'=nx^ {n-1}$
$_ \Delta x$ 是一个无穷小量。把式子展开后，分子只有 $_ \Delta x$ 的一次项和零次项是有用的。
$(\ln x)'=\frac{1}{x}$
指数函数和对数函数关于 $y=x$ 对称。
$(f(g(x))'=f'(g(x))\times g'(x)$
$\frac{_ \Delta f}{_ \Delta x}=\frac{_ \Delta f}{_ \Delta g}\times \frac{_ \Delta g}{_ \Delta x}$
$(a^ x)'=\ln a\times a^ x$
对于任意指数函数都可以把底换成 $e^ {???}$ 的形式，然后用复合函数合并导数。
$(log_ a x)'=\frac{1}{x\times \ln a}$
对数函数之间只是常数差别，可以通过换底公式把 $\log_ e x$ 转化成 $\log_ a x$ 。
$(\sin x)'=\cos x,(\cos x)'=-\sin x$
不会证。

泰勒展开

泰勒展开只是一个工具。
一些特殊的函数我们可以尝试用多项式去逼近。
一个标准的泰勒展开形式是这样的（ $x_ 0$ 是我们选定的一个值）：

A(x)=\sum_ {i=0}^ \infty a_ i (x-x_ 0)^ i

然而大多数时候会发现 $x_ 0$ 为0时是展开的最好选择……
下面以 $\sin x$ 为例。

\sin x=\sum_ {i=0} ^ \infty a_ i x^ i

为了求 $a_ 0$ 的值，我们可以把x=0带入原式……
得到 $0=a_ 0\times 1,a_ 0=0$
怎么求 $a_ 1$ ？对等式左右两边求导……

\cos x=\sum_ {i=1} ^ \infty i a_ i x^ {i-1}

再把x=0带进去……
得到 $1=1! \times a_ 1\times 1,a_ 1=1$
再求导……

-\sin x=\sum_ {i=2}^ \infty i(i-1)a_ i x^ {i-2}

把x=0带入得到 $0=2! \times a_ 2 \times 1,a_ 2=0$
会发现求导时出现的系数在算时能形成阶乘的形式，sin和cos之间也有明显的循环节
继续写下去就是这样了：

\sin x=x-\frac{x^ 3}{3!}+\frac{x^ 5}{5!}-\frac{x^ 7}{7!}+\cdots

会发现对于 $e^ x$ 这个函数进行泰勒展开就比较奇怪，因为它求导后是它自己……
按照刚刚的方法会算出这种玩意：

e^ x=\sum_ {i=0} ^ \infty \frac{x^ i}{i!}

泰勒展开证明欧拉公式

把 $e^ x$ 在x的为实数时的泰勒展开搬到虚数部分。

e^ {ix}=1+ix-\frac{x^ 2}{2!}-\frac{ix^3}{3!}+\frac{x^4}{4!}+\cdots

这时候把cos和sin的泰勒展开写出来:

\cos x=1-\frac{x^ 2}{2!}+\frac{x^4}{4!}+\cdots,\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}

于是就愉快地发现 $e^ {ix}=\cos x+i\sin x$

牛顿迭代

一个待啃的通俗讲法
牛顿迭代只有在函数存在二阶导（导数的导数）时才比较正常。
大体思路是随便猜一个解，然后把解更新成对原函数在这个位置的切线的0点，如此反复。

现在对于一个多项式 $A(x)$ ，想求 $A(x)=0$ 的解。
首先猜一个解 $x_ 0$ ,对多项式进行泰勒展开。（~~谁说只有特殊函数才要泰勒展开来着~~）

A(x)=A(x_ 0)+ A'(x_ 0)(x-x_ 0)+\cdots

同样，和求切线一样，认为自己猜的这个答案很接近正确答案，那么后面的项 $(x-x_ 0)^ k(k\in \mathbb{N})$ 会衰减地很快，平方项都可以不用考虑。

A(x)\approx A(x_ 0)+ A'(x_ 0)(x-x_ 0)=A(x_ 0)+ A'(x_ 0)x-A'(x_ 0)x_ 0

x\approx \frac{A'(x_ 0)x_ 0+A(x_ 0)}{A'(x_ 0)}=x_ 0-\frac{A(x_ 0)}{A'(x_ 0)}

后面那个其实就是求切线0点……

多项式逆元

一个多项式模 $x^ n$ 的意义可以看作只取 $x^ 0$ 到 $x^ {n-1}$ 的项。
现在想对于 $A(x)$ 求出他在模 $x^ n$ 意义下的逆元 $B(x)$ ，即 $A(x)\times B(x) \equiv 1(\mod x^ n)$
赵设：“搞不定它，先搞定它小弟……”
一个多项式模x的逆元显然就是常数项的逆元。
现在考虑知道 $A(x)$ 在模 $x^ {\frac{n}{2}}$ 下的逆元 $B_ 0(x)$ ，现在想要求出在 $x^ n$ 下的逆元 $B(x)$ 。

B(x) \equiv B_ 0(x)(\mod x^ \frac{n}{2})

B(x)-B_ 0(x) \equiv 0(\mod x^ \frac{n}{2})

(B(x)-B_ 0(x))^ 2 \equiv 0(\mod x^ n)

（上一步是因为 $B(x)-B_ 0(x)$ 的前 $\frac{n}{2}$ 项都为零，最小的可能有值的项是 $x^ \frac{n}{2}$ 这项卷自己得到，大于等于 $x^ n$ ）

B(x)^ 2-2B(x)B_ 0(x)+B_ 0(x)^ 2 \equiv 0(\mod x^ n)

两边同时与 $A(x)$ 卷积

A(x)B(x)-2B_ 0(x)+A(x)B_ 0(x)^ 2 \equiv 0(\mod x^ n)

B(x) \equiv 2B_ 0(x)-AB_ 0(x)^ 2

会发现 $A(x)$ 在模 $x^ {n+1}$ 意义下的逆元也是在模 $x^ n$ 意义下的逆元，直接把逆元往大取再模 $x^ n$ 就行。

多项式取模

~~留坑待填~~