浅谈母函数
母函数真是迷人……
定义
母函数是一个无穷级数:
我们把系数提取出来,这个系数序列与母函数存在一一对应的关系,存在双射:$\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件物品的方案数。
他这次又准备带一些受欢迎的食物,如:蜜桃多啦,鸡块啦,承德汉堡等等。
当然,他又有一些稀奇古怪的限制:
每种食物的限制如下:
注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以‘个’为单位(反正是幻想嘛),只要总数加起来是$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$即得解。