母函数总结

母函数总结

概述

母函数,又称生成函数,是ACM竞赛中经常使用的一种解题算法,常用来解决组合方面的题目。
母函数有两种,一种是指数型母函数一种是普通型母函数

普通型母函数

普通型母函数通常解决类似如下的问题:
给5张1元,4张2元,3张5元,要得到15元,有多少种组合?
某些时候会规定至少使用3张1元、1张2元、0张5元。
某些时候会规定有无数张1元、2元、5元。

普通型母函数有两种,一种是有限制的(硬币个数有限制的取),一种是无限制的(硬币个数无限的取)

普通型母函数的一般数学表示为:

有限制的:

无限制的:

例题:

  1. HDU1028 Ignatius and the Princess III(整数划分,母函数模板题,无限制)

    整数划分问题,给你一个数n,让你求出这个数有几种不同的划分。每个数有无限个可以用.

  1. HDU1398 Square Coins(母函数,无限制的)

有面值为$1^2,2^2,3^2,…,17^2$的硬币无限个,然后给出一个n,问有多少种组成方法可以组成n.

  1. HDU1085 Holding Bin-Laden Captive!(母函数,有限制的)

现在有面值为1元,2元,5元的硬币若干枚,问这些硬币不能组成的最小金额是多少。

优化版:

指数型母函数

关于指数型母函数:指数型母函数 简介

指数型母函数的一般问题为:

有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数

模板:

例题:

HDU1521 排列组合(指数型母函数,有限制的)

指数型母函数因为每种物品有数量,所以引入了阶乘,比如给出一组样例:

那么就应该:
$$
(1+\frac{x^1}{1!})(1+\frac{x^1}{1!}+\frac{x^2}{2!}) =1+2x+\frac{3}{2}x^2+\frac{1}{2}x^3
$$
因为$x^2$项的系数为$\frac{3}{2}$,所以答案就是$\frac{3}{2}
2!=3$.

#代码

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注