多项式全家桶
听起来很吓人的名字（在我学之前），慢慢知识积累上去，你会发现它就是一堆数学推导。
不断更新中...
当前进度：多项式exp / 常系数齐次线性递推
基础知识
微积分
（暂时）并不需要太高的水平，最基本的会即可。
基础求导：
(C'=0)
((x^n)'=nx^{n-1})
((e^x)'=e^x)
(ln'(x)=dfrac{1}{x})
((Cf(x))'=Cf'(x))
((fpm g)'=f'pm g')
((fg)'=f'g+fg')
((dfrac{f}{g})'=dfrac{f'g-fg'}{g^2})
(f(g(x))'=f'(g(x))g'(x))
基础积分：
把上面这些反过来
FFT/NTT
这还要讲？
泰勒展开
现在已知一个函数 (f(x))。要用一个多项式函数 (g(x)) 逼近它
考虑先选取一个起点 (x_0)，以这个位置为参考 （一般这个位置要好算一些，或者有可以利用的数值）
然后我们的主体思路是，让 (f,g) 在 (x_0) 处的值，一阶导，二阶导，三阶导...都相同。
首先我们让 (f,g) 在 (x_0) 处相同。那 (g) 先加上一项 (f(x_0)) 的常数。
然后我们让它的一阶导相同，那我们要给它来点多项式了。但是注意我们不能改变取值，于是我们只能加上 (x-x_0) 的若干倍。
设 (g_k) 表示一个函数，它在 (x_0) 处的 (k) 阶导和 (f) 相同。
考虑 (g_1)：
当 (x=x_0) 时，(g_1'(x)=f'(x_0))
同时积分，(g_1(x)=xf'(x_0)+C)
为了凑 (x-x_0)，我们令 (g_1(x)=(x-x_0) f'(x_0))
考虑 (g_2)：
同时积分两次
(g_2(x_0)=dfrac{1}{2} f''(x_0)x_0^2 + C(x))，(C(x)) 是任意至多一次的多项式。
同理，我们令 (g_2(x)=dfrac{1}{2}f''(x_0) (x-x_0)^2)
这里出现了分数，容易发现这个分数是积分的时候积出来的，积了多少次，就会有多少个，所以是一个阶乘
所以 (g_k(x)=dfrac{f^{(k)}(x_0) (x-x_0)^k}{k!})
然后把所有的 (g_k) 和常数项加起来，得到：
牛顿迭代
首先，我们对一个多项式 (mod {x^n})，意思就是取前 (n-1) 项，这个东西想想就明白了。
另外，因为同余 (equiv) 很不好打，后面 (=) 也表示同余 —— 这个写法很不好，但看到后面有 (pmod{...}) 便可知这个 (=) 表示同余。
回到正题。现在我们要解一个多项式方程 (E(f)=0)，其中 (f) 是一个未知多项式，我们要找出来它。
而实际问题中我们一般只需要 (f) 的前 (k) 项，也就是 (mod x^k) 的解。
假设我们知道了 (E(f_0)=0 pmod{x^n})，要找一个 (E(f)=0 pmod{x^{2n}})
假设能这么求，那么求 (log) 次，就可以求出 (mod x^k) 的解了。
我们在 (f_0) 处展开 (E)，并求 (f) 位置的值 （没错，展开结果是一个多项式套多项式，会有若干个 (f) 的若干次方）
(E(f)=E(f_0)+E'(f_0)(f-f_0)+dfrac{E''(f_0)(f-f_0)^2}{2!}+...)
我们强制令 (f=f_0 pmod{x^n})，容易证明，如果 (E) 有解，那这样一定能找到一个解。
证：
假设 (E(g)=0 pmod{x^{m}})，其中 (m) 是一个足够大的数 —— 比我们要用的所有 (n) 大
考虑 (f=gmod x^n)
在 (g) 处展开 (E)，代入 (f) 求值
(E(f)=E(g)+E'(g)(f-g)+...)
由于 (f=g pmod{x^n})，所以 (f-g=0 pmod{x^n}) ，于是 (E(f)=E(g)=0 pmod{x^n})
也就是我们要找的 (mod x^n) 的解，当然，(m) 再大一点，容易证明，把 (n) 换成 (2n) ，或者是我们想要的 (k) ，都是成立的，都能找到解
然后注意到 ((f-f_0)^2=0pmod{x^{2n}})，后面的次数更大，都包含这个因子 —— 所以从 (2) 开始我们全都不用要了。
然后 (E(f)=E(f_0)+E'(f_0)(f-f_0))
移项并整理：
然后每次这么求一遍就可以了。关于如何算除法，后面再说。
牛顿迭代的代码实现
假设我们现在已经知道了多项式乘法，这里直接假设封装了 operator （实际上我并没有这么干，因为我试过一次，很慢，也不知如何优化）
相当于半个伪代码和C++
void solve(euqation E,poly& g,int n)
// E 是那个方程
// 实际代码实现中, 通常是传一个方程的参数进来, 然后通过推式子手动求方程的值和求导之类的
// 另外, 一般这里的g是传数组进来, 就不用&了
{
int len,lim;
poly g=trival(); // 先瞪出来一个trival的边界值
for(len=1;len<=(n<<1);len<<=1)
{
lim=len<<1; // 这个是 FFT/NTT 要用的
E_=deri(E); // 求导
// 实际上我们是需要手动求导的, 而且不会写成这样, 这里仅供示意
g=g-E(g)*inv(E_(g)); // inv: 求逆, 后面讲, 乘以一个多项式的逆相当于除
// 顺便, 一般这里求 E 啥的还要再来一堆辅助数组
}
return g;
}
别问我为啥要贴这个，我初学的时候尝试自己想怎么写，但是一直不知道lim和len咋搞
如果您自己想出来了，恭喜你，把我吊打了
多项式正题
多项式乘法
FFT/NTT 直接上
多项式求逆
已知 (f)，求 (g) 使 (fg=1 pmod{x^k})
记 (g=f^{-1})。由于逆元的对称性，(f=g^{-1})
牛顿迭代需要用除法，而多项式求逆就是用来解决除法的，所以牛顿迭代比多项式求逆高 —— 换句话说我们没法用牛顿迭代算多项式求逆。这就好比你没法生下来你妈，因为你是你妈生的 超 级 加 辈
但是这个思路值得借鉴。假设有(g_0) 使 (fg_0=1 pmod{x^n})，求 (g) 使 (fg=1 pmod{x^{2n}})。还是令前 (n) 项相同，然后考虑 ((g-g_0)^2)，显然它 (=0 pmod{x^{2n}})。
展开它，变成
(g^2-2gg_0+g_0^2=0pmod{x^{2n}})
同时乘以 (f)
(fg^2-2fgg_0+fg_0^2=0pmod{x^{2n}})
我们设 (fg=1 pmod{x^{2n}})，所以可以代入一下变成
(g-2g_0+fg_0^2=0pmod{x^{2n}})
移项得：
然后迭代即可。上面提到，除相当于乘以逆元。于是就可以算除法了。
多项式对数函数(ln)
要求 (g(x)=ln(f(x)) pmod{x^k})
以 (x) 为主元来导，(g'(x)=dfrac{1}{f(x)}f'(x))
然后积回去：
（为啥打中间是因为这样的积分好看，打在行间就是 (int)）
多项式指数函数(exp)
非常好听的名字：exp。它也有很完美的性质，一切都是 (e) 这个神秘数字的魅力。
先回到正题。要求：(g=exp(f)=e^f pmod{x^n})
相当于 (ln(g)-f=0)
设 (E(g)=ln(g)-f)。易得 (E'(g)=dfrac{1}{g})（这里设 (g) 为主元，然后 (f) 就是常数，也不用链式法则了）
换句话说求的是 (dfrac{dE(g)}{dg})
(g=g_0-dfrac{E(g_0)}{E'(g_0)}=g_0-dfrac{ln(g_0)-f}{dfrac{1}{g_0}})
整理一下就是
然后它的完美性质是甚么？
假设我们知道一个东西 (A) ，它的数量的的生成函数是 (F)
然后有另一个东西 (B)，它的数量的生成函数是 (G)
然后 (B) 是由若干个 (A) 无序拼起来的。
这样的例子很多，比如说置换是由循环置换拼起来的，任意图是由若干连通图拼起来的，森林是由树拼起来的...
然后 (G=exp(F))
为什么呢？枚举 (A) 用了多少个，假设是 (i) 个。然后它们的大小的和要等于 (n)，也就是一个多元卷积的形式。又因为是无序的，所以要除以 (i!)
于是有 (G=sumlimits_{i=1}^{infin}dfrac{F^i}{i!})
然后这玩意就是 (exp(x)) 在 (x_0=0) 处的展开 （容易验证）。于是 (G=exp(F))
当然它还有更多完美的性质，此处略
不太有用的东西
指多项式开根/三角函数
题目里没见到过，只有板子里有。 也可能是我too young too simple
反正牛迭随便推一下就行了
多项式快速幂
先开 (ln)，然后乘以 (k) （我们要的幂），然后再 (e) 回来。一个 (log)，比倍增快速幂快。
多项式带余除法
给定 (F,G)，次数分别是 (n,m)。
求 (Q,R) 使得 (F=QG+R)，其中 (R) 的次数必须小于 (m) —— 容易证明存在唯一的 (G,R)。
（其中我们称 (Q) 为商，(R) 为余数）
考虑模 (x^n) 这个操作，它可以去掉多项式从 (n) 开始的更高的次数，只保留 ([0,n-1]) 次。换句话说，它体现在数组上去掉了一个 后缀。
然后现在比较不好处理的就是这个 (R) 。我们希望用一个类似取模的东西，去掉一个 前缀，直接多项式乘法逆就可以求出 (Q) 了。
那这不是很好办么，前缀反过来就是后缀了。但是请注意，(R) 的次数很小，反过来的时候注意补项。
于是得到了问题的解决办法：
- (F,G) 做一遍 (reverse)，设得到了 (F_r,G_r)。然后 (Q=F_r imes (G_r)^{-1})
- (R=F-QG)，直接乘然后减就完了
常系数齐次线性递推
单独出来写吧，有点长
见 ko↑ko↓
多项式多点求值 / 快速插值
咕咕咕~
多项式复合 / 多项式复合逆
咕咕咕~
普通多项式和下降幂多项式的转化
斯特林数瞎搞一番就行了
（本质上也是咕咕咕）
鸽 王 争 霸 赛