算法合集之母函數(shù)的性質(zhì)及應(yīng)用

算法合集之母函數(shù)的性質(zhì)及應(yīng)用第1頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)[定義]母函數(shù)是用于對(duì)應(yīng)一個(gè)無窮序列的冪級(jí)數(shù)，一般來說母函數(shù)有形式：第2頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)舉一個(gè)例子：閉形式不考慮收斂問題！第3頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)[基本操作]1．放縮：第4頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)2．加減法：第5頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)3．右移:第6頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)4.求導(dǎo)：第7頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)舉一個(gè)求導(dǎo)的例子：第8頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)5．卷積規(guī)則：組合問題第9頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)[簡單的序列所對(duì)應(yīng)的母函數(shù)]不定方程非負(fù)整數(shù)解的個(gè)數(shù)第10頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用[例1]原創(chuàng)題[例3]Sweets第11頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用[例1]小明出門旅游，需要帶一些食物，包括薯片，巧克力，礦泉水，漢堡，牛奶和糖果。經(jīng)過估計(jì)，他覺得帶n(n<=10100)件食物比較合適，但他還有一些癖好：最多帶1個(gè)漢堡巧克力的塊數(shù)是5的倍數(shù)最多帶4瓶礦泉水薯片的包數(shù)是一個(gè)偶數(shù)最多帶3罐牛奶糖果的個(gè)數(shù)是4的倍數(shù)問你小明有多少種方式來準(zhǔn)備這次旅行所帶的食物。第12頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用漢堡巧克力薯片礦泉水牛奶糖果第13頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用運(yùn)用卷積規(guī)則第14頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)[指數(shù)型母函數(shù)]復(fù)雜簡單！第15頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)最基本的指數(shù)型母函數(shù)Taylor公式名稱來源第16頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)乘積排列問題！第17頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用[例2]Chocolate[例4]證明題第18頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)[母函數(shù)型Pólya定理]（Pólya定理）設(shè)G是n個(gè)對(duì)象的一個(gè)置換群，用m種顏色涂染這n個(gè)對(duì)象，則不同染色方案數(shù)為不夠具體！第19頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)把m種顏色具體表示出來！母函數(shù)型Pólya定理第20頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)一個(gè)具體的例子：有4顆珠子繞成一圈，用兩種顏色染色，旋轉(zhuǎn)后重疊的方案算一種。置換群G：Pólya定理第21頁，共26頁，2023年，2月20日，星期六母函數(shù)的性質(zhì)母函數(shù)型Pólya定理得具體的方案2黑2白的有兩種，4黑，4白，3黑1白，3白1黑的都只有1種第22頁，共26頁，2023年，2月20日，星期六母函數(shù)的應(yīng)用[例5]IOI2003國家集訓(xùn)隊(duì)難題討論活動(dòng)0015Polygon第23頁，共26頁，2023年，2月20日，星期六總結(jié)離散數(shù)學(xué)連續(xù)數(shù)學(xué)母函數(shù)解決問題優(yōu)化算法證明命題第24頁，共26頁，2023年，2月20日，星期六參考文獻(xiàn)[1]吳文虎，王建德.《信息學(xué)奧林匹克競賽指導(dǎo)─組合數(shù)學(xué)的算法與程序設(shè)計(jì)》.清華大學(xué)出版社，2002[2]劉汝佳，黃亮.《算法藝術(shù)與信息學(xué)競賽》.清華大學(xué)出版社，2004[3]RonaldL.Graham，DonaldE.Knuth，OrenPatashnik.《ConcreteMathematics─AFoundationforComputerScience(2ndEdition)》.Addison-WesleyProfessional，1994[4]盧開澄.《組合數(shù)學(xué)（第三版）》.清華大學(xué)出版社，2002[5]周源.NOI冬令營講稿.2008[6]雷環(huán)中，金愷.IOI中國國