算法合集之《母函数的性质及应用》PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,母函数的性质及应用,2009,国家集训队论文,毛杰明,南京外国语学校,Email:maojm517,邮政编码：,210008,1,母函数的性质,定义,母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：,2,母函数的性质,举一个例子：,闭形式,不考虑收敛问题！,3,母函数的性质,基本操作,1,放缩：,4,母函数的性质,2,加减法：,5,母函数的性质,3,右移,:,6,母函数的性质,4.,求导：,7,母函数的性质,举一个求导的例子：,8,母函数的性质,5,卷积规则：,组合问题,9,母函数的性质,简单的序列所对应的母函数,不定方程非负整数解的个数,10,母函数的应用,例,1,原创题,例,3Sweets,11,母函数的应用,例,1,小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带,n(n=10,100,),件食物比较合适，但他还有一些癖好：,最多带,1,个汉堡,巧克力的块数是,5,的倍数,最多带,4,瓶矿泉水,薯片的包数是一个偶数,最多带,3,罐牛奶,糖果的个数是,4,的倍数,问你小明有多少种方式来准备这次旅行所带的食物。,12,母函数的应用,汉堡,巧克力,薯片,矿泉水,牛奶,糖果,13,母函数的应用,运用卷积规则,14,母函数的性质,指数型母函数,复杂,简单！,15,母函数的性质,最基本的指数型母函数,Taylor,公式,名称来源,16,母函数的性质,乘积,排列问题！,17,母函数的应用,例,2Chocolate,例,4,证明题,18,母函数的性质,母函数型,Plya,定理,（,Plya,定理）设,G,是,n,个对象的一个置换群，用,m,种颜色涂染这,n,个对象，则不同染色方案数为,不够具体！,19,母函数的性质,把,m,种颜色具体表示出来！,母函数型,Plya,定理,20,母函数的性质,一个具体的例子：有,4,颗珠子绕成一圈，用两种颜色染色，旋转后重叠的方案算一种。,置换群,G,：,Plya,定理,21,母函数的性质,母函数型,Plya,定理得具体的方案,2,黑,2,白的有两种，,4,黑，,4,白，,3,黑,1,白，,3,白,1,黑的都只有,1,种,22,母函数的应用,例,5 IOI2003,国家集训队难题讨论活动,0015 Polygon,23,总结,离散数学,连续数学,母函数,解决问题,优化算法,证明命题,24,参考文献,1,吴文虎，王建德,.,信息学奥林匹克竞赛指导组合数学的算法与程,序设计,.,清华大学出版社，,2002,2,刘汝佳，黄亮,.,算法艺术与信息学竞赛,.,清华大学出版社，,2004,3 Ronald L.Graham,，,Donald E.Knuth,，,Oren Patashnik.Concrete,MathematicsA Foundation for Computer Science(2nd Edition).,Addison-Wesley Professional,，,1994,4,卢开澄,.,组合数学（第三版）,.,清华大学出版社，,2002,5,周源,.NOI,冬令营讲稿,.2008,6,雷环中，金恺,.IOI,中国国家集训队难题讨论活动解题报告，,2003,25,Thats all.Thank you!,欢迎提问！,26,