指数型母函数总结

指数型母函数网上的资料不是很多,推荐毛杰明的09年国家集训队论文《母函数的性质及应用》

以及Richard A.Brualdi 所著的《组合数学》的第七章来看…倒不用全看懂..但是这本上面干货比较多。

我来说下自己的理解:

指数型母函数和普通型母函数(不加普通二字也是指它)的区别是后者是用来求解组合问题(顺序无关行),而前者是求解排列问题(不同的顺序属于不同的方案)。

对于多重排列问题,由于某种元素可能有多个,需要去掉它的重复度(除以该种元素的个数的阶乘),而这个除以阶乘的形式和泰勒级数展开中的一些函数的展开形式一致(或者是一些变形)。

因此母函数可以用泰勒级数来化简。

这是求解这类问题最核心的内容。

 

也有直接算的。比如这个hdu1521排列组合hdu1521排列组合解题报告但是由于阶乘的存在。。这类问题求解的范围十分有限。
所以更多的是下面这些题,难度递增,建议先独立思考…
hdu2065解题报告
poj1322 chocolate解题报告
cf451E解题报告

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz