看了网上一些博文，总觉得写得很乱。最近刚好学习了相关内容，决定亲自动手写一篇。
前置知识
多项式
表达式：
以下内容仅需了解：卷积（多项式乘法），多项式求逆，多项式ln，多项式exp，牛顿迭代...
（当然，这是不可能的）
- 分治+NTT
比较厉害的一个技巧。
- 给定 n 个一次多项式 ai + bix，求
- n<=105
暴力卷积，时间复杂度 > O(n2)的......
原因就在于卷着卷着次数会不断变大。
想象一下，我们平时做多个数的乘法，没有人会去顺序一个一个乘吧......
那可以用类似分治的办法，对于每个区间将左右合并起来。
时间复杂度：T(n)=2T(n/2)+O(nlogn)=O(nlog2n)
具体的实现可以用 vector 存多项式，空间复杂度是 O(nlogn)的。
类似的，还可以拓展出分式求和：
给定 n 个一次多项式 ai+bix，求 
如果直接求逆是 O(n2logn)的，
同上，对于每个区间维护分子和分母，最后再求逆算答案。
时间复杂度 O(nlog2n)，空间复杂度 O(nlogn)。
Taylor 展开
其实这个不是重点。
然后有个背下来经典的东西：
可以直接泰勒展开，不过也可用别的方法推：
广义二项式定理
我们都知道喜闻乐见的二项式定理：
但有时候，我们想让这个 n 变成负数甚至小数咋办？
设 
我们有 
解释一下求导：
...
带入，得：
啊哈，于是我们还能定义拓展的组合数 
普通型生成函数（OGF）
定义：已知数列{an}，构造形式幂级数
G(x)=a0+a1x+a2x2+...+anxn+...
称G(x)为序列{an}的生成函数。
标签：...,函数,多项式,复杂度,生成,nlogn From： https://www.cnblogs.com/buleeyes/p/17533453.html