母関数の原初

   看了论文和数学书后晕乎乎的

   为了理解定义，透彻地理解，这篇博文仅限于一些基础公式和小问题（开胃菜？）

   零、预备知识

呐，假装知道了母函数的所有知识，看看一些不加证明的公式

普通的母函数

   1、

   2、令g(n)为母函数第n项的系数，由插板法可得

   3、最终结论

   一、例题一

from http://www.wutianqi.com/

   我们有1g、2g、3g、4g砝码各一枚，问可称出哪几种重量？每种重量含有那些方案？

   The First kiss

   假设x表示砝码（物品），x的指数表示单个砝码的重量（属性）

   一个1g砝码的函数：f(x)=1+x

　一个2g砝码的函数：f(x)=1+x*x，以此类推

此处的1代表指数0？，也就是重量为x的砝码选取0个

   组合后的函数就是：f(x) = (1+x) (1+x^2) (1+x^3) (1+x^4)

　　　　　　　　　　　　 = 1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + x^8 + x^9 + x^10

   回归最初的定义，那么，称出质量为k的砝码，对应的x的k次项的系数就是方案数

就这样，一个递推问题转化为了和多项式相关的问题

   二、例题二

from 09年国家集训队论文 毛杰明 题目2.1

   出门旅游的小明要带食物，n件比较合适(n<=10^100) 。

   规定如下：

最多带1 个汉堡
巧克力的块数是5 的倍数
最多带4 瓶矿泉水
薯片的包数是一个偶数
最多带3 罐牛奶
糖果的个数是4 的倍数
   问你小明有多少种方式来准备这次旅行所带的食物。

Solution

这里的问题就要动真格了，用点真家伙

这里的母函数求和会大量的用到等差数列或级数的方式求和，暂且不考虑其收敛性

求和的公式或方法见我的博文http://www.cnblogs.com/keshuqi/p/6195074.html

1、汉堡对应的函数

2、牛奶对应的函数

3、巧克力的函数

4、薯片

5、矿泉水

6、牛奶嘛

7、甜的东西？糖果

   利用卷积规则，此类函数的乘积为

这里用之前的公式展开

再用二项式定理展开

哎，其实用各项的系数公式一步就得到了

   就是这个

若不考虑组合数的求值，单纯询问复杂度为O(1)，还是很优的哦

先这样吧

明天要参加英才计划的什么东东夏令营

估计会沉默一段时间呢，等会吧

题外话：

从自己的角度来说，我也不是很清楚继续oi这条路的意义

不过

要是意义太明确了，变得太功利了的话，不就无聊了吗？

人生只有一次，浪费在为别人而活的过程中实在是不够潇洒啊

虽然不是很清楚人生的意义，同样地，如果那个意义太明确了，不就无聊了吗

人生固然没有实际意义，但继续走下去，就会发现很多有趣的事情，和更多的未知、神秘相遇，和更多的人相逢

这不美吗？

2017年的立春，我正在确立自我的十字路口上，高中生了嘛

。。。

母函数的基础内容