母函数

浅谈母函数

母函数真是迷人……

定义

母函数是一个无穷级数
我们把系数提取出来,这个系数序列与母函数存在一一对应的关系,存在双射:$\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)\leftrightarrow0,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^0x^5,x^1x^4,x^2x^3,x^3x^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$即得解。

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/07/19/719-1/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------