浅谈母函数

母函数真是迷人……

定义

母函数是一个无穷级数$\displaystyle G(x)=g_0+g_1x+g_2x^2+\cdots=\sum_{i=0}^\infty g_ix^i$

我们把系数$g_0,g_1\cdots$提取出来,这个系数序列与母函数存在一一对应的关系,存在双射:$\vec{g} \leftrightarrow G(x)$.

举个例子,有母函数$G(x)=1+x+x^2+x^3\cdots$,则与之对应的系数表达就是$<1,1,1,1\cdots>$.

基本运算

加减
$F(x)+G(x) \leftrightarrow <f_0+g_0,f_1+g_1,f_2+g_2\cdots>$
$F(x)-G(x) \leftrightarrow <f_0-g_0,f_1-g_1,f_2-g_2\cdots>$

数乘
$c*G(x) \leftrightarrow <c*g_0,c*g_1,c*g_2\cdots>$

乘幂
$x^k*G(x)\leftrightarrow<0,0\cdots,0,g_0,g_1\cdots>$(前面放上$k$$0$

卷积
$F(x) \times G(x)$,跑FFT做多项式乘法即可。

用处

这里介绍最简单的用途。

你有一些水果,只能拿3的倍数个苹果,只能拿质数个草莓。问对于每个$0<i<=n$,有多少种方案使得恰好拿$i$个水果。

我们不妨先造出两个布尔数组,来储存“能不能拿”。
苹果:[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1...]
草莓:[0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0...]

考虑母函数。我们尝试用$x^k$的系数来表示$k$个物品的方案数。那么上面的两个布尔数组生成了两个母函数:

苹果:$A(x)=x^3+x^6+x^9\cdots$
草莓:$B(x)=x^2+x^3+x^5+x^7\cdots$

我们把它们乘起来,就会发现一个奇妙的事情:乘积的结果,$x^k$的系数正好表示了取$k$个物品的方案数。

为什么会这样?考虑$x^5$的系数。$x^5$可以由$x^0*x^5,x^1*x^4,x^2*x^3,x^3*x^2\cdots$来构成,这正好映射了“0个苹果5个草莓、1个苹果4个草莓……”的选取方式。

结合FFT,我们就可以在$O(n \log n)$的时间复杂度内求出$0<i<=n$的答案。直接输出卷积即可。

高级运算:求导
母函数可以求导。效果是把系数左移一位,然后乘上次数。
$G(x)\space \space \leftrightarrow \space <g_0,g_1,g_2,g_3\cdots>$
$G'(x)\space \leftrightarrow \space <g_1,2g_2,3g_3\cdots>$

闭形式

考虑母函数$<1,1,1\cdots>$,对其进行等比数列求和:
$\displaystyle 1+x+x^2+x^3\cdots = \frac{1}{1-x}$

我们称$\frac{1}{1-x}$为母函数$<1,1,1\cdots>$闭形式
注意,这里忽略了收敛问题。但是这没有影响,因为我们需要使用的是系数,与$x$的取值始终无关。

对母函数的操作等价于对闭形式的操作。例如,我们对$<1,1,1\cdots>$求导:
$\displaystyle G(x)=\frac{1}{1-x}$
$\displaystyle G'(x)=\frac{1}{(1-x)^2}$

$G'(x) \leftrightarrow <1,2,3\cdots>$(之前已经算出过)

故有结论:$\displaystyle \frac{1}{(1-x)^2} \leftrightarrow <1,2,3\cdots>$.

例题

论文题。

明明这次又要出去旅游了,和上次不同的是,他这次要去宇宙探险!

我们暂且不讨论他有多么NC,他又幻想了他应该带一些什么东西。理所当然的,你当然要帮他计算携带N件物品的方案数。

他这次又准备带一些受欢迎的食物,如:蜜桃多啦,鸡块啦,承德汉堡等等。
当然,他又有一些稀奇古怪的限制:

每种食物的限制如下:

最多带 1 个汉堡
巧克力的块数是 5 的倍数
最多带 4 瓶矿泉水
薯片的包数是一个偶数
最多带 3 罐牛奶
糖果的个数是 4 的倍数

注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以‘个’为单位(反正是幻想嘛),只要总数加起来是$n$就算一种方案。因此,对于给出的$n$,你需要计算出方案数,并对$10007$取模。$n<=10^{100}$$k<=3$

我们考虑为每个限制生成自己的母函数。像前面的例子一样,$0$代表可选择,$1$代表不可选择。
汉堡:$<1,1,0,0,0,0\cdots> \leftrightarrow 1+x$
(只能带$0$$1$个)
巧克力:$<1,0,0,0,0,1,0,0,\cdots> \leftrightarrow \frac{1}{1-x^5}$
($5$的倍数)
矿泉水:$<1,1,1,1,1,0,0\cdots> \leftrightarrow \frac{1-x^5}{1-x}$
(最多$4$瓶)
薯片:$<1,0,1,0,1\cdots> \leftrightarrow \frac{1}{1-x^2}$
(偶数个)
牛奶:$<1,1,1,1,0,0\cdots> \leftrightarrow \frac{1-x^4}{1-x}$
(最多$3$罐)
糖果:$<1,0,0,0,1,0\cdots> \leftrightarrow \frac{1}{1-x^4 }$
($4$的倍数)

直接卷起来,最后结果化简为$\displaystyle \frac{1}{(1-x)^3} = (\frac{1}{1-x})^3\leftrightarrow <1,1,1,1,1\cdots>^3$

容易用二项式定理把它重新搞成系数形式:$1+C^2_3x+C^2_4x^2+C^2_5x^3\cdots$

题目需要求的是$x^n$的系数,直接输出$C_{n+2}^2$即得解。

指数型母函数

泰勒展开相关。留坑待补。


Update on 2016.8.30

此坑已补。


Update on 2016.10.3

修正了一些错误。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close