JZTXT

生成函数

发布时间 2023-07-06 21:58:06作者: 青阳buleeyes

看了网上一些博文，总觉得写得很乱。最近刚好学习了相关内容，决定亲自动手写一篇。

前置知识

多项式

表达式：

　　　　A(x)=\sum_{i=1}^{n} a_{i}x_{i}

 

以下内容仅需了解：卷积（多项式乘法），多项式求逆，多项式ln，多项式exp，牛顿迭代...

（当然，这是不可能的）

  • 分治+NTT

比较厉害的一个技巧。

  • 给定 n 个一次多项式 ai + bix，求 \prod_{i=1}^{n}(a_{i}+b_{i}x)
  • 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}的生成函数。