浅谈母函数
母函数真是迷人……
定义
母函数是一个无穷级数：
我们把系数提取出来，这个系数序列与母函数存在一一对应的关系，存在双射：$\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$即得解。
