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

《算法合集之母函数的性质及应用精.ppt》由会员分享，可在线阅读，更多相关《算法合集之母函数的性质及应用精.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法合集之母函数的性质及应用第1页，本讲稿共26页母函数的性质母函数的性质v定义 v母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：第2页，本讲稿共26页母函数的性质母函数的性质v举一个例子：闭形式不考虑收敛问题！第3页，本讲稿共26页母函数的性质母函数的性质v基本操作v1放缩：第4页，本讲稿共26页母函数的性质母函数的性质v2加减法：第5页，本讲稿共26页母函数的性质母函数的性质v3右移:第6页，本讲稿共26页母函数的性质母函数的性质v4.求导：第7页，本讲稿共26页母函数的性质母函数的性质v举一个求导的例子：第8页，本讲稿共26页母函数的性质母函数的性质v5卷积规则：组合问题第

2、9页，本讲稿共26页母函数的性质母函数的性质v简单的序列所对应的母函数不定方程非负整数解的个数第10页，本讲稿共26页母函数的应用母函数的应用v例1原创题 v例3Sweets第11页，本讲稿共26页母函数的应用母函数的应用v例1小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带n(n=10100)件食物比较合适，但他还有一些癖好：最多带1个汉堡巧克力的块数是5的倍数最多带4瓶矿泉水薯片的包数是一个偶数最多带3罐牛奶糖果的个数是4的倍数v问你小明有多少种方式来准备这次旅行所带的食物。第12页，本讲稿共26页母函数的应用母函数的应用v汉堡v巧克力v薯片v矿

3、泉水v牛奶v糖果第13页，本讲稿共26页母函数的应用母函数的应用v运用卷积规则第14页，本讲稿共26页母函数的性质母函数的性质v指数型母函数复杂简单！第15页，本讲稿共26页母函数的性质母函数的性质v最基本的指数型母函数Taylor公式 名称来源第16页，本讲稿共26页母函数的性质母函数的性质v乘积 排列问题！第17页，本讲稿共26页母函数的应用母函数的应用v例2Chocolatev例4证明题第18页，本讲稿共26页母函数的性质母函数的性质v母函数型Plya定理v（Plya定理）设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为 不够具体！第19页，本讲稿共26页母函数的

4、性质母函数的性质v把m种颜色具体表示出来！母函数型Plya定理 第20页，本讲稿共26页母函数的性质母函数的性质v一个具体的例子：有4颗珠子绕成一圈，用两种颜色染色，旋转后重叠的方案算一种。置换群G：Plya定理 第21页，本讲稿共26页母函数的性质母函数的性质v母函数型Plya定理得具体的方案 2黑2白的有两种，4黑，4白，3黑1白，3白1黑的都只有1种 第22页，本讲稿共26页母函数的应用母函数的应用v例5 IOI2003国家集训队难题讨论活动0015 Polygon第23页，本讲稿共26页总结总结离散数学连续数学母函数v解决问题v优化算法v证明命题第24页，本讲稿共26页参考文献v1 吴

5、文虎，王建德.信息学奥林匹克竞赛指导组合数学的算法与程 序设计.清华大学出版社，2002v2 刘汝佳，黄亮.算法艺术与信息学竞赛.清华大学出版社，2004v3 Ronald L.Graham，Donald E.Knuth，Oren Patashnik.Concrete MathematicsA Foundation for Computer Science(2nd Edition).Addison-Wesley Professional，1994v4 卢开澄.组合数学（第三版）.清华大学出版社，2002v5 周源.NOI冬令营讲稿.2008v6 雷环中，金恺.IOI中国国家集训队难题讨论活动解题报告，2003第25页，本讲稿共26页Thats all.Thank you!欢迎提问！第26页，本讲稿共26页