ACM母函數(shù)080421ppt課件

1、ACM程序設計程序設計杭州電子科技大學 劉春英上一周，上一周，你你 了嗎？了嗎？練習每周一星每周一星7 7）：）：0705420207054202第八講第八講母函數(shù)及其應用母函數(shù)及其應用（Generation function）從遞推關系說起從遞推關系說起研究以下多項式乘法：研究以下多項式乘法：可以看出：可以看出：x2x2項的系數(shù)項的系數(shù)a1a2+a1a3+.+an-1ana1a2+a1a3+.+an-1an中所有的項包括中所有的項包括n n個個元素元素a1a1，a2a2， anan中取兩個組合的全體；中取兩個組合的全體；同理：同理：x3x3項系數(shù)包含了從項系數(shù)包含了從n

2、n個元素個元素a1a1，a2a2， anan中取中取3 3個元素組合的全體；個元素組合的全體；以此類推。以此類推。 (81)若令a1=a2= =an=1，在8-1式中a1a2+a1a3+.+an-1an項系數(shù)中每一個組合有1個貢獻，其他各項以此類推。故有：（82）特例：母函數(shù)定義：母函數(shù)定義：n對于序列對于序列a0a0，a1a1，a2a2，構造一函數(shù)：構造一函數(shù)： n稱函數(shù)稱函數(shù)G(x)G(x)是序列是序列a0a0，a1a1，a2a2，的的母函數(shù)母函數(shù) For example:(1+x)n是序列C(n,0),C(n,1),.,C(n,n)的母函數(shù)。 如若已知序列a0，a1，a2，則對應的母函數(shù)

3、G(x)便可根據(jù)定義給出。反之，如若已經(jīng)求得序列的母函數(shù)G(x)，則該序列也隨之確定。 序列a0，a1，a2，可記為an 。 實實 例例 分分 析析例例1 1：若有：若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝碼各一克的砝碼各一 枚，枚，能稱出哪幾種重量？各有幾種可能方案？能稱出哪幾種重量？各有幾種可能方案？ 如何解決這個問題呢？考慮構造母函數(shù)。如果用x的指數(shù)表示稱出的重量，那么：1個1克的砝碼可以用函數(shù)1+x表示，1個2克的砝碼可以用函數(shù)1+x2表示，1個3克的砝碼可以用函數(shù)1+x3表示，1個4克的砝碼可以用函數(shù)1+x4表示，幾種砝碼的組合可以稱重的情況，可幾種砝碼的組合可以稱

4、重的情況，可以用以上幾個函數(shù)的乘積表示：以用以上幾個函數(shù)的乘積表示：(1+x)(1+x2)(1+x3)(1+x4)(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 =1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 從上面的函數(shù)知道：可稱出從從上面的函數(shù)知道：可稱出從1 1克到克到1010克，系數(shù)便克，系數(shù)便是方案數(shù)。是方案數(shù)。例如右端有例如右端有2x5 2x5 項，即稱出項，即稱出5 5克的方案有克的方

5、案有2 2：5=3+2=4+15=3+2=4+1；同樣，；同樣，6=1+2+3=4+26=1+2+3=4+2；10=1+2+3+410=1+2+3+4。故稱出故稱出6 6克的方案有克的方案有2 2，稱出，稱出1010克的方案有克的方案有1 1 例例2：求用：求用1分、分、2分、分、3分的郵票貼分的郵票貼出不同數(shù)值的方案數(shù)出不同數(shù)值的方案數(shù) n因郵票允許重復，故母函數(shù)為：因郵票允許重復，故母函數(shù)為：n以展開后的以展開后的x4x4為例，其系數(shù)為為例，其系數(shù)為4 4，即，即4 4拆拆分成分成1 1、2 2、3 3之和的拆分數(shù)為之和的拆分數(shù)為4 4；n即即 ：4=1+1+1+1=1+1+2=1+3=2

6、+24=1+1+1+1=1+1+2=1+3=2+2概念：整數(shù)拆分概念：整數(shù)拆分 n所謂整數(shù)拆分即把整數(shù)分解成若干整所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和相當于把數(shù)的和相當于把n n個無區(qū)別的球放個無區(qū)別的球放到到n n個無標志的盒子，盒子允許空，個無標志的盒子，盒子允許空，也允許放多于一個球）。也允許放多于一個球）。n整數(shù)拆分成若干整數(shù)的和，辦法不一，整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分數(shù)。不同拆分法的總數(shù)叫做拆分數(shù)。 練習寫出以下問題的母函數(shù)）：練習寫出以下問題的母函數(shù)）：n例例3 3：若有：若有1 1克砝碼克砝碼3 3枚、枚、2 2克砝碼克砝碼4 4枚、枚、4 4克砝

7、碼克砝碼2 2枚，問能稱出哪幾種重量？枚，問能稱出哪幾種重量？各有幾種方案？各有幾種方案？ n例例4: 4: 整數(shù)整數(shù)n n拆分成拆分成1 1，2 2，3 3，m m的和，求其母函數(shù)。的和，求其母函數(shù)。n例例5 5：如若上例中：如若上例中m m至少出現(xiàn)一次，至少出現(xiàn)一次，其母函數(shù)又如何？其母函數(shù)又如何？ 如何編寫程序如何編寫程序實現(xiàn)母函數(shù)的應用呢？實現(xiàn)母函數(shù)的應用呢？核心問題核心問題關鍵：對多項式展開關鍵：對多項式展開以整數(shù)拆分為例：以整數(shù)拆分為例：觀察以下的母函數(shù)：觀察以下的母函數(shù)：首先思考：如果讓你手工計算，你是怎樣處理的？首先思考：如果讓你手工計算，你是怎樣處理的？實際編程：讓計算機按照

8、自己的思路計算即可實際編程：讓計算機按照自己的思路計算即可/ Author by lwg#include using namespace std;const int lmax=10000; int c1lmax+1,c2lmax+1;int main()int n,i,j,k;while (cinn)for (i=0;i=n;i+) c1i=0;c2i=0; for (i=0;i=n;i+) c1i=1; for (i=2;i=n;i+)for (j=0;j=n;j+)for (k=0;k+j=n;k+=i) c2j+k+=c1j; for (j=0;j=n;j+) c1j=c2j;c2j=0

9、; coutc1nendl;return 0;主打例題：主打例題：HDOJ_1398 Square Coins HDOJ_1398 Square Coins Sample InputSample Input2 2101030300 0 Sample OutputSample Output1 14 42727算法分析：算法分析：典型的利用母函數(shù)可解的題目。典型的利用母函數(shù)可解的題目。G(x)=(1+x+x2+x3+x4+)(1+x4+x8+x12+)(1+x9+x18+x27+)/HDOJ_1398 Square Coins#include using namespace std;const i

10、nt lmax=300;int c1lmax+1,c2lmax+1;int main(void)int n,i,j,k;while (cinn & n!=0)for (i=0;i=n;i+)c1i=1;c2i=0;for (i=2;i=17;i+)for (j=0;j=n;j+)for (k=0;k+j=n;k+=i*i)c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nn & n!=0)for (i=0;i=n;i+)c1i=1;c2i=0;for (i=2; i=17; i+)for (j=0;j=n;j+)for (k=0;k+j=n; k+

11、=elemi-1 ) c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nendl;return 0;考慮考慮1）：）：nHDOJ_1028HDOJ_1028nIgnatius and the Ignatius and the Princess IIIPrincess III考慮考慮2）：）：nHDOJ_1085HDOJ_1085nHolding Bin-Laden Holding Bin-Laden Captive!Captive!考慮考慮3）：）：nHDOJ_1171HDOJ_1171nBig EventBig Eventnin HDUin HDU考慮考慮4）：）：nHDOJ_1709HDOJ_1709The BalanceThe BalanceAny questions?Any questions?附：相關作業(yè)附：相關作業(yè)(hdoj)：2019Exercise(9)_2