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

第1页，共26页，星期日，2025年，2月5日母函数的性质[定义]母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：第2页，共26页，星期日，2025年，2月5日母函数的性质举一个例子：闭形式不考虑收敛问题！第3页，共26页，星期日，2025年，2月5日母函数的性质[基本操作]1．放缩：第4页，共26页，星期日，2025年，2月5日母函数的性质2．加减法：第5页，共26页，星期日，2025年，2月5日母函数的性质3．右移:第6页，共26页，星期日，2025年，2月5日母函数的性质4.求导：第7页，共26页，星期日，2025年，2月5日母函数的性质举一个求导的例子：第8页，共26页，星期日，2025年，2月5日母函数的性质5．卷积规则：组合问题第9页，共26页，星期日，2025年，2月5日母函数的性质[简单的序列所对应的母函数]不定方程非负整数解的个数第10页，共26页，星期日，2025年，2月5日母函数的应用[例1]原创题[例3]Sweets第11页，共26页，星期日，2025年，2月5日母函数的应用[例1]小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带n(n=10100)件食物比较合适，但他还有一些癖好：最多带1个汉堡巧克力的块数是5的倍数最多带4瓶矿泉水薯片的包数是一个偶数最多带3罐牛奶糖果的个数是4的倍数问你小明有多少种方式来准备这次旅行所带的食物。第12页，共26页，星期日，2025年，2月5日母函数的应用汉堡巧克力薯片矿泉水牛奶糖果第13页，共26页，星期日，2025年，2月5日母函数的应用运用卷积规则第14页，共26页，星期日，2025年，2月5日母函数的性质[指数型母函数]复杂简单！第15页，共26页，星期日，2025年，2月5日母函数的性质最基本的指数型母函数Taylor公式名称来源第16页，共26页，星期日，2025年，2月5日母函数的性质乘积排列问题！第17页，共26页，星期日，2025年，2月5日母函数的应用[例2]Chocolate[例4]证明题第18页，共26页，星期日，2025年，2月5日母函数的性质[母函数型Pólya定理]（Pólya定理）设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为不够具体！第19页，共26页，星期日，2025年，2月5日