Preface:


很久没有写过讲解类的博客了,心血来潮准备写一写^o^(我绝对不是为了访问量而写的)

预备知识:

你需要熟悉多项式加减法以及等比数列(这个很简单),然后还有快速数论/傅里叶变换(如果不熟悉只知道作用也可以理解理论内容),以及简单的导数、微积分知识(摊手)和较强的数学理解能力(滑稽)。

本文参照WC2016策爷的PPT的简单部分,加入了个人的一些理解,欢迎各位dalao吐槽。

一般生成函数(OGF):


如果你之前没有接触过生成函数,这种表示方法可能比较新奇,实际上就是把一个无穷数列 \({A_i}\) 表示为一个函数。

定义:

\[ A(x)=\sum_{i\ge 0} A_i x^i\]

为什么这样表示呢?因为这样的多项式对应的运算对数列 \(A_i\) 具有组合意义。(注意有时OGF是可以化简的,如 \(\sum_{i\ge 0} 2^i x^i = \frac{1}{1-2x}\) )

我们把 \(A_i\) 定义为一类组合对象中大小为 \(i\) 的数量,例如,这一类对象为01串,大小定义为字符串长度,那么 \(A_i\) 就表示长度为 \(i\) 的字符串个数。

基本运算:

那么我们来观察加和乘对应的组合意义(设 \(A(x)\)\(B(x)\) 为两个OGF):

  1. 加法:如果 \(C(x)=A(x)+B(x)\) ,那么 \(C_n = A_n+B_n\) ,所以很容易看出, \(C(x)\) 对应的一类组合对象,为A和B的并集。
  2. 乘法:如果我们定义A和B的笛卡尔积为D(笛卡尔积为两个集合之间的运算,大家可以自己去搜一搜),对于D中一个元素 \((a,b), a\in A, b\in B\) ,定义 \(|(a, b)|=|a|+|b|\) ,那么就可以发现 \(D_n = \sum_{i=0}^n A_i B_{n-i}\) ,即 \(D(x)=A(x)B(x)\)

对于一些计数问题,我们就可以考虑对于其生成函数(取前面的n位)进行相应运算,再取出对应位置的结果。(这其中涉及大量多项式乘法运算,一般运用NTT解决)

当然只有这两种运算以及组合变换是远远不够的,接下来我们从某一种组合变换推知其对应的运算。

元素的排列:

我们定义 \(\mathcal{SEQ}(A)\)\(A\) 中元素组成的序列的集合的OGF,其中一个序列的大小为其中每一个元素的大小总和。
可以看出序列长度分为 \(0, 1, 2, \ldots\) ,对应为 \(A\) 的几次方。
即:

\[\mathcal{SEQ}(A)=1+A+A\cdot A+A^3+\cdots=\frac{1}{1-A}\]

举个栗子:

\(A\) 为字符串"0"或"1",则 \(A(x)=2x\) ,那么 \(\mathcal{SEQ}(A)\) 表示01串,可以得到 \(\mathcal{SEQ}(A)=\frac{1}{1-2x}=\sum_{i\ge 0} 2^i x^i\)

指数生成函数(EGF):


注意到我们目前讨论的相同大小的组合对象是不加以区分的,也就是说是无标号的,但是涉及例如无向图计数之类的就不能够使用了。

于是我们就有了指数生成函数。

定义:

\[A(x)=\sum_{i\ge 0}\frac{A_i}{i!} x^i\]

为什么带一个阶乘,这是由于带标号对象拼接的性质决定的,看了下面的内容你就会明白了。

基本运算:

  1. 加法:同样是表示并集,即 \(\frac{C_n}{n!} = \frac{A_n}{n!} + \frac{B_n}{n!}\)
  2. 乘法:(这里就是为什么带阶乘的原因)注意到乘法,即 \(\frac{D_n}{n!}=\sum_{i=0}^n \frac{A_i}{i!}\times \frac{B_{n-i}}{(n-i)!}\) ,化简一下,可以得到 \(D_n = \sum_{i=0}^n A_iB_{n-i} \frac{n!}{i!(n-i)!}\) ,因为 \(\frac{n}{i!(n-i)!} = \binom{n}{i}\) ,所以就相当于大小为n中的每一个单位都是有编号的。举个栗子,若 \(A(x)\)\(B(x)\) 都是有标号无向连通图的EGF,那么 \(D(x)\) 就表示由两个连通块组成的有标号无向图的EGF。所以乘法就表示带标号对象的拼接。

元素的排列:

定义和OGF中的是一样的,可以发现元素的排列一点儿也没有变。注意这是排列,也就是说,我们每一次元素间拼接是有顺序的,而不是说每一个单位大小(例如标号)是有顺序的。

一模一样的公式:

\[\mathcal{SEQ}(A) = \frac{1}{1-A}\]

元素的组合:

注意这个和排列的区别,元素间是没有顺序关系的,即是组合,但是单位大小是有顺序关系的(例如标号)。

\(\mathcal{SET}(A)\)\(A\) 中元素组成集合的EGF。

可以得到:

\[\mathcal{SET}(A)=\sum_{i\ge 0} \frac{A^i}{i!} = e^A\]

关于从第二步到第三步的推导,可以用麦克劳林展开来推导,由于后面总是用到麦克劳林展开来推导式子,还是写出来一下吧O_O

麦克劳林展开:

\[f(x) = \sum_{i\ge 0} \frac{f^{(n)}(0)x^i}{i!}\]

然后我们把 \(f(x)=e^x\) 带进去就可以了。

然而 \(e^A\) 这种奇怪的东西怎么求呢?接下来就讲一些奇奇怪怪的算法。

多项式相关算法:


多项式求导以及积分:

如果你有接触过微积分和导数的话,这些都十分简单。

因为 \((ax^n)' = anx^{n-1}\) ,所以我们可以对于 \(f\) 乘上对应位置的指数,然后把数组左移一位就可以了。

因为 \(\int ax^n \, \mathrm{d}x = \frac{a}{n+1} x^{n+1}+C\) ,不妨取常数为0,我们可以把数组右移一位以后除去对应位置的指数。

多项式求逆:

大家对于整数在模 \(mod\) 意义下的逆元都非常的熟悉,下面介绍如何求多项式的逆。

若对于多项式 \(A(x),B(x)\) ,满足 \(A(x)B(x)\equiv 1 \pmod {x^n}\) ,则称 \(B(x)\)\(A(x)\) 的逆。

假设我们已经求得 \(A(x)B_0(x) \equiv 1 \pmod {x^{\lfloor \frac{n}{2} \rfloor}}\)

因为 \(A(x)B(x)\equiv 1 \pmod {x^{\lfloor \frac{n}{2}\rfloor}}\) ,然后我们开始推导:

然后我们求出 \(A(x)\) 常数项的逆元就可以一路算出来(用NTT计算多项式乘法) \(B(x)\) 了。

可以得到 \(T(n) = T(\frac{n}{2})+O(n\log n)\) ,所以时间复杂度为 \(O(n \log n)\)

 

 

什么?没有代码??

 

 

 

那就贴一段:

传入的数组就是需要求逆的数组,n是长度(最高次为n-1)。

多项式求 ln:

为什么我们需要求ln呢?因为在EGF的组合中,可能存在逆过程,就有这个必要了(可以见后面的例题)。

假设我们已知 \(f(x)\) ,需要求 \(g(x) = \ln f(x)\)

因为 \(g(x) = \ln f(x)\) ,对两边同时求导(复合函数的求导法则):

\[ g'(x) = \frac{f'(x)}{f(x)}\]

所以有:

\[g(x) = \int \frac{f'(x)}{f(x)}\, \mathrm{d}x\]

然后我们求导、求逆、然后NTT、再积分就可以了,时间复杂度 \(O(n \log n)\)

这是一道例题(里面有代码(●'◡'●)):BZOJ3456 城市规划

多项式求exp:

所谓多项式的exp,就是指的e的多项式次方,例如对于 \(f(x)\) ,求 \(e^{f(x)}\) 就是多项式求exp。多项式求exp比多项式求ln要复杂一些,利用牛顿迭代可以实现 \(O(n\log n)\)

牛顿迭代:

这个牛顿迭代不是指的求方程根的牛顿迭代,而是用于求满足某方程的函数的算法。

设未知的形式幂级数 \(f\) 满足某方程 \(\mathfrak{G}(f) = 0\) ,我们需要求 \(f\)

假设已经求得前n项,即:

\[f\equiv f_0 \pmod {x^n}\]

我们对方程 \(\mathfrak{G}\)\(f_0\) 处进行泰勒展开(也是比较基础的高数内容):

又因为

\[\mathfrak{G}(f) = 0\]

所以

\[f \equiv f_0-\frac{\mathfrak{G}(f_0)}{\mathfrak{G}'(f_0)} \pmod {x^{2n}}\]

也就是说,我们可以通过迭代求得 \(f\) 了。

 

设我们需要求 \(f(x) = e^{A(x)}\) ,则 \(\ln f(x) - A(x) = 0\)

也就是说, \(\mathfrak{G}(f) = \ln f - A = 0\) ,带入牛顿迭代的式子,就可以得到:

\[ f = f_0(1-\ln f_0 +A)\]

时间复杂度还是 \(O(n\log n)\)

 

多项式求逆也可以用牛顿迭代推导,结果也是一样一样的:)

未完待续……