生成函数

Published: by Creative Commons Licence

  • Tags:

概率生成函数

对于取值为自然数的随机变量X,定义概率生成函数为

很显然

其中$P(x=i)$为随机变量取到i的概率。利用概率生成函数可以简单地计算期望:

可以递推推出对于$i\geq 2$有

比较重要的就是计算方差的公式:

普通生成函数(ODF)

对于序列$a_0,a_1,\ldots$,它的生成函数为$f(x)=\sum_{i\geq 0}a_ix^i$,记$[f(x)]_i$表示其$x^i$项的系数$a_i$。

  • 两个序列<$a_i$>与<$b_i$>的生成函数的加法运算的结果得到的是<$a_i+b_i$>的生成函数。
  • 两个序列<$a_i$>与<$b_i$>的生成函数的乘法运算的结果得到的是<$\sum_{0\leq j\leq i}a_jb_{i-j}$>的生成函数。

一般我们在做生成函数的运算的时候,采用封闭形式能够加快计算的效率。下面是几个比较常用的封闭形式:

  • <$1$>的生成函数为$\sum_{i\geq 0}x^i=\frac{1}{1-x}$
  • <$[k|i]$>的生成函数为$\sum_{i\geq 0}x^{ki}=\frac{1}{1-x^k}$
  • <$i$>的生成函数为$\sum_{i\geq 0}ix^i=\frac{x}{(1-x)^2}$
  • <${n \choose i}$>的生成函数为$\sum_{i\geq 0}{n \choose i}x^i=(1+x)^n$
  • <${n+i \choose i}$>的生成函数为$\sum_{i\geq 0}{n+i \choose i}x^i=\frac{1}{(1-x)^{n+1}}$
  • <$\frac{1}{i!}$>的生成函数为$\sum_{i\geq 0}\frac{1}{i!}x^i=e^x$
  • <$\frac{1}{i}$>的生成函数为$\sum_{i\geq 1}\frac{1}{i}x^i=-\ln(1-x)=\ln(\frac{1}{1-x})$

题目1:计算$a_1+\ldots+a_n+b_1+\ldots+b_m+c_1+\ldots+c_k=T$的方案数,其中所有变量为非负整数,且$a_1,\ldots,a_n$只能取奇数,$b_1,\ldots,b_m$只能取偶数,$c_1,\ldots,c_k$为任意非负整数。问有多少种不同的赋值方案,其中$1\leq n,m,k\leq 100$,将结果模上素数$p$。

我们要计算的是生成函数$f(x)=(\frac{x}{(1-x^2)})^n(\frac{1}{1-x^2})^m(\frac{1}{1-x})^k=\frac{x^n(1+x)^k}{(1-x^2)^{n+m+k}}$的第$T$项系数。或者是$g(x)=\frac{(1+x)^k}{(1-x^2)^{n+m+k}}$的第$T-n$按项系数。

进一步展开可以得到:

搞出$\sum_{i\geq 0}{k\choose i}x^i$,枚举$O(k)$个$\sum_{i\geq 0}{n+m+k-1+i\choose i}x^{2i}$的系数就可以算出来了。时间复杂度为$O(k\log_2p+n+m)$,还是相当快的。

一道题目

题目2:给定$n$个非负未知整数$a_1,\ldots,a_n$,要求$a_i\leq R_i$,且$a_1+\ldots+a_n=T$。问有多少种方案,结果模上素数$p$,这里$R_i\leq 10^6$,$T\leq 10^7$,$1\leq n\leq 10$,$p\leq 10^6$。

这个问题可以用DP解决,时间复杂度为$O(nT)$。

也可以用组合数学+容斥解决,时间复杂度为$O(2^n+p)$。

这里讲一下生成函数的做法。可以发现我们要计算的是$\prod_{i=1}^n\frac{1-x^{R_i+1}}{1-x}=\frac{\prod_{i=1}^n1-x^{R_i+1}}{(1-x)^n}$。容易发现上面的分子最多只有$2^n$项的系数非$0$,我们可以用哈希表来表示,计算的时间复杂度为$O(n2^n)$。我们可以将分母展开,得到:

我们可以遍历左边的项求解结果,总的时间复杂度为$O(n2^n+p)$。

指数生成函数(EGF)

对于序列$a_0,a_1,\ldots$,其指数生成函数为$f(x)=\sum_{i\geq 0}\frac{a_i}{i!}x^i$。

  • 两个序列<$a_i$>与<$b_i$>的生成函数的加法运算的结果得到的是<$a_i+b_i$>的生成函数。
  • 两个序列<$a_i$>与<$b_i$>的生成函数的乘法运算的结果得到的是<$\sum_{0\leq j\leq i}{i \choose j}a_jb_{i-j}$>的生成函数。

一些常用的指数生成函数和其封闭形式的转换。

  • <$1$>的指数生成函数为$\sum_{i\geq 0}\frac{1}{i!}x^i=e^x$
  • <$i!$>的指数生成函数为$\sum_{i\geq 0}x^i=\frac{1}{1-x}$
  • <$(i-1)!$>的指数生成函数为$\sum_{i\geq 0}\frac{1}{i}x^i=-\ln(1-x)=\ln(\frac{1}{1-x})$

生成函数的系数区间和

给定一个生成函数,我们要计算某个封闭形式为$f(x)$的生成函数,系数和$\sum_{i=L}^R[f(x)]_i$。

这是一个比较经典的技巧,就是我们将$f(x)$乘上$\sum_{i=0}^{R-L}x^i=\frac{1-x^{R-L+1}}{1-x}$,之后取$x^R$项的系数即可。

参考资料