浅谈母函数

母函数真是迷人……

定义

母函数是一个无穷级数：$G\left(x\right)=g_0+g_{1}x+g_2{x}^2+\cdots =\sum _{i=0}^{\infty }{g}_i{x}^i$

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

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

基本运算

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

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

乘幂
$x^k\ast G\left(x\right)\leftrightarrow <0,0\cdots ,0,g_0,g_1\cdots >$（前面放上$k$个$0$）

卷积
$F\left(x\right)\times G\left(x\right)$，跑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\left(x\right)=x^3+x^6+x^9\cdots$
草莓：$B\left(x\right)=x^2+x^3+x^5+x^7\cdots$

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

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

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

高级运算：求导
母函数可以求导。效果是把系数左移一位，然后乘上次数。
$G\left(x\right)\leftrightarrow <g_0,g_1,g_2,g_3\cdots >$
$G^{\prime }\left(x\right)\leftrightarrow <g_1,2g_2,3g_3\cdots >$

闭形式

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

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

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

又$G^{\prime }\left(x\right)\leftrightarrow <1,2,3\cdots >$（之前已经算出过）

故有结论：$\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$的倍数)

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

容易用二项式定理把它重新搞成系数形式：$1+C_3^{2}x+C_4^2{x}^2+C_5^2{x}^3\cdots$

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

指数型母函数

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

---

Update on 2016.8.30

此坑已补。

---

Update on 2016.10.3

修正了一些错误。