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