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