Generating Fuction!~生成函数乱编

无限填坑中 随时准备咕咕 _________________ 个人做过的生成函数题比较少，如果这篇文章有锅的话请各位数数精及时指出 本文主要介绍传统的生成函数,也就是大家在传统计数问题当中最常使用的OGF,EGF,并不会介绍狄利克雷生成函数，概率生成函数这些代数工具(因为我不会) _本文里可能不区分生成函数和形式幂级数这两个词的区别，在不引起歧义的情况下多项式这个词可能指幂级数或者形式幂级数_ ___________________ ## 引子 提到生成函数可能很多人会想到非常难调，一旦出bug就只能对着代码fc的多项式板子们，不过生成函数和多项式算法的关系并不密切，只是现在很多计数题存在先编一个生成函数出来然后用多项式板子强行做出来的做法，导致生成函数这个知识点和多项式家族捆绑在了一起 不过本文并不会花太多的篇幅在多项式全家桶上，如果想要学习这些技术的话你站有全套的多项式模板，从ntt到exp，从分治fft到快速插值应有尽有 既然我们的重点是放在生成函数上，那么生成函数到底有什么用呢？ 其实生成函数最大的特点就是用**代数手段**解决组合问题,就像解析几何当中用代数手法解决几何问题一样，生成函数将本来需要想半年的组合技巧变成写半年的纸上推导，从而让数数精们可以出更多的毒瘤数数题 那么让我们开始介绍生成函数吧~ # 一般生成函数 Ordinary Generating Fuction ## 导入~生成函数,形式幂级数 我们在计数题当中经常会碰到一些数列 比如常数列$1,1 ...1$ 比如等比数列$1,2,4,..2^n$ 比如二项式系数的一行${n \choose 1},{n \choose 2}..{n \choose n}$ 我们在做多项式题的时候会碰到一些多项式 比如$f(x)=1+x^1+x^2...x^n$ 比如$f(x)=1+2x^1+4x^2..2^nx^n$ 比如$f(x)={n \choose 1}+{n \choose 2}x^2+{n \choose 3}x^3...{n \choose n}x^n$ 当我们存一个数列的时候，我们会开一个数组，数组的第i项存数列的第i项 当我们存一个多项式的时候，我们会开一个数组，数组的第i项存多项式的第i项系数 我们会发现尽管多项式的存储方式似乎和数列的方式没有什么本质的区别，但是我们却可以把两个多项式相乘，相除，开根，做exp取ln 另一个诡异的事实是我们不能把两个数列相乘除或者做一些奇奇怪怪的运算，尽管数列和多项式可以构建一一对应的映射，怎么想怎么不对劲啊，所以我们搞出了生成函数 定义一个数列$a$的一般生成函数$G(z)$是 $$G(z)=\sum_{i}a(i)z^i$$ 嗯这样我们就把一个数列映射到了一个多项式上，但是多项式的限制太多了，我们需要考虑定义域和收敛性等一系列杂七杂八的东西，我们搞了一个生成函数出来不是来看多项式的限制的，我们只想对生成函数背后的数列进行操作 形式幂级数就是为此而生的，简单来说形式幂级数的精髓就在于它定义了一套运算规则可以让我们对数列进行类似于多项式的加减乘除开根exp取ln，但是却不用像多项式一样考虑它是否有意义，事实上我们平时使用的多项式算法都是形式幂级数之间的运算 ## 运算(加减乘除求导积分expln) 形式幂级数的加减乘法和多项式的运算并没有什么区别，他们都对应着数列的按位相减，以及卷积 对于除法来讲，我们发现很多时候我们并不能给两个多项式相除，因为对于一个多项式$P(x)$可能不存在一个有限的多项式$P^{-1}(x)$使得$P(x)P^{-1}(x)=1$，但是如果我们允许$P^{-1}(x)$是一个无限多项式的话，我们就能找到这样的一个$P^{-1}(x)$ 那么我们就可以使用$P(x)/Q(x)=P(x)Q^{-1}(x)$来计算除法了 生成函数的求导和积分和多项式也是一样的，此处不再赘述 接下来是一些奇怪的东西，exp和ln，我们知道这些函数本身不是一个有限多项式可以刻画的，但是形式幂级数是一个无穷多项式，那么是否存在一个无穷多项式可以去刻画exp和ln呢？答案是肯定的 我们不妨考虑函数$e^{x}$和$ln(x)$的麦克劳林级数(说人话就是在x=0把这两个函数泰勒展开一下) ~~啊？你不会泰勒展开？请自行百度一下~~ 我们先来考虑$e^{z}$变成多项式以后是什么样子，将$e^{z}$在$z=0$处泰勒展开就得到了这样的式子 $$e^{z}=\sum_{i}\frac{z^{i}}{i!}$$ 看起来我们通过这个式子就可以很轻松的将exp推广到多项式上 $$G(z)=\sum_{i}a(i)z^{i}$$ $$\exp(G(z))=\sum_{i}\frac{G^{i}(z)}{i!}$$ $$\exp(G(z))=\sum_{k}z^{k}\sum_{1b_{1}+2b_{2}...+mb_{m}=k}\frac{\prod_{i=1}^{m}a(i)^{b(i)}}{m!}$$ 然后让我们来考虑$ln(x)$能不能也推广到多项式上,有点遗憾的是$ln(x)$在x处没有定义……，而如果展开的位置不为0我们又不能简单的将ln(x)写成一个多项式 所以我们采用这个公式 $$\ln(1-z)=-\sum_{i}\frac{z^{i}}{i}$$ 那么我们借助这个式子就可以把ln运算强行推广一下 $$1-G(z)=\sum_{i}a(i)z^{i}$$ $$\ln(1-G(z))=-\sum_{i}\frac{G^{i}(z)}{i}$$ $$\ln(1-G(z))=-\sum_{k}z^{k}\sum_{1b_{1}+2b_{2}+...mb_{m}=k}\prod_{i=1}^{m}\frac{a(i)^{b(i)}}{m}$$ 那么我们现在也可以对形式幂级数进行取ln操作了，类似的我们可以通过泰勒展开来定义多项式的幂函数，三角函数等等操作 ## 编生成函数 很多计数题的套路是这样的，先搞一个数列，通过这个数列我们能得到答案，然后我们把这个数列的生成函数编出来发现它是一堆形式幂级数进行运算得到的，然后我们使用多项式科技就做完了这道题 显然编生成函数就是解题的关键了，绝大部分情况下只有数数精们才能编的出来，但是对于一些简单的数列我们还是可以试着编一编生成函数的 ### 查表求解生成函数 如果我们的数列很特殊，那么很多时候前人已经帮我们求出了这个数列的生成函数，此时直接记住或者查表是最好的手段 这里是一些常用的生成函数表 ### 通过递归式求解生成函数 下面以fib数列和catanlan数列的生成函数推倒为例演示一下如何求解一个有递归式的数列的生成函数 #### fibonacci 数列的生成函数 我们知道fibonacci数列有这样一个递归式 $$fib(i)=fib(i-1)+fib(i-2)$$ 但是这个递归式是不完全的，我们还需要一些边界条件，否则我们会无限递归下去，我们知道这个递归式的边界条件是 $$fib(1)=1,fib(0)=0$$ 那么我们不妨设$G(z)$为fibonacci数列的一般生成函数，我们可以得到这样的式子 $$G(z)=G(z)z+G(z)z^2+z$$ 那么这个式子有什么意义呢？我们知道生成函数间的乘法运算对应着卷积，特殊的，如果$G(z)$被乘上了$z^x$这意味着将整个数列平移x位 那么我们重新翻译一下上面的等式在描述什么 **将fib数列整体平移一位得到的数列和fib数列平移2位得到的数列按位相加，并且令该数列的第一项为1，我们就得到了fib数列自己** 你可以手玩一下会发现上面的等式的确成立，那么我们就得到了关于$G(z)$的一个等式，稍微做一下变换我们就可以得到fib数列的生成函数其实是 $$G(z)=\frac{z}{1-z-z^2}$$ #### catanlan 数列的生成函数 我们以卡特兰数为例解释一下如何处理"自己卷自己"的递归式 我们知道catanlan数列存在着这样的一个递归式 ### 通过生成函数间的运算拼凑生成函数 ## 快速求解生成函数 ### 带除法的生成函数与线性递推 ### ln的泰勒展开与一类特殊的求和问题 ### 带根号的生成函数的计算 考虑施罗德数的生成函数…………… ### 第一类斯特林数的求解方法 # 指数型生成函数 Exponential Generating Fuction ## 导入~二项卷积和指数型生成函数 ## 指数生成函数与多项式ln和exp # 例题 ## P3784 [SDOI2017]遗忘的集合 ## uoj424 【集训队作业2018】count ## P4566 [CTSC2018]青蕈领主 ## codeforces gym 102056 B Mysterious...Host ## P4002 生成树计数 ## P5206 [WC2019] 数树 ## P4500 [ZJOI2018]树