母函数，又称生成函数，是ACM竞赛中经常使用的一种解题算法，常用来解决组合方面的题目。

使用母函数解决问题的方法称为母函数方法。

        对于序列C0、C1、C2、…、Cn，构造函数G(x)=C0+C1x+C2x2+…+Cnxn，称G(x)为序列C0、C1、C2、…、Cn的母函数。

        先来看一道例题。

例1  砝码称重

        有1克、2克、3克和4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？

        4个不同重量的砝码，最小可称重1克，最多可称重10克（1+2+3+4）。由于数据量较小，我们可以直接枚举。枚举情况如表1所示。

表1  4个砝码称重

可称重量

方案组合情况

方案数

1

1（表示选用重量为1克的砝码，下同）

1

2

2

1

3

1+2、3

2

4

1+3、4

2

5

1+4、2+3

2

6

1+2+3、2+4

2

7

1+2+4、3+4

2

8

1+3+4

1

9

2+3+4

1

10

1+2+3+4

1

下面，我们用母函数来解决这个问题。

1个1克砝码可以看成1+x1，1表示不取，x1表示取一个，以下同理。

1个2克砝码可以看成1+x2

1个3克砝码可以看成1+x3

1个4克砝码可以看成1+x4

构造母函数g(x)=(1+x1)(1+x2)(1+x3)(1+x4)

                         =1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10

        在这个函数中，若指数表示可称出重量，系数表示方案数，则可以看出重量为3克、4克、5克、6克、7克的方案数均有两种，而重量为1克、2克、8克、9克、10克的方案只有1种。与表1中枚举情况吻合。

        当然，例1这个问题比较简单。因为，4个砝码在称重时，每个砝码或选用或不用，因此，称重组合有2*2*2*2=16种情况，可以很方便地枚举。如果砝码种类再多一些，或每种砝码的个数有多个，仍然采用枚举的话并不容易。

        例如，我们设有1克、2克和3克的砝码各3个，用这9个砝码能称出哪几种重量？每种重量各有几种可能方案？

        9个3种重量的砝码，最小可称重1克，最多可称重18克（1+2+3）*3=18。虽说数据量略有增大，我们还是先枚举。枚举情况如表2所示。

表2  9个砝码称重

可称重量

方案组合情况

方案数

1

1

1

2

1+1、2

2

3

1+1+1、1+2、3

3

4

1+1+2、1+3、2+2

3

5

1+1+1+2、1+1+3、1+2+2、2+3

4

6

1+1+1+3、1+1+2+2、1+2+3、2+2+2、3+3

5

7

1+1+1+2+2、1+1+2+3、1+2+2+2、1+3+3、2+2+3

5

8

1+1+1+2+3、1+1+2+2+2、1+1+3+3、1+2+2+3、2+3+3

5

9

1+1+1+2+2+2、1+1+1+3+3、1+1+2+2+3、1+2+3+3、2+2+2+3、3+3+3

6

10

与8对应（9个砝码去掉8中的每种情况，不一一列举）

5

11

与7对应

5

12

与6对应

5

13

与5对应

4

14

与4对应

3

15

与3对应

3

16

1+1+1+2+2+3+3+3、1+2+2+2+3+3+3 （与2对应）

2

17

1+1+2+2+2+3+3+3   （与1对应）

1

18

1+1+1+2+2+2+3+3+3

1

        下面，我们用母函数来解决这个问题。

        3个1克砝码可以看成1+x1+x2+x3，1表示1个不取，x1表示取1个，x2表示取2个，x3表示取3个，以下同理。

        3个2克砝码可以看成1+x2+x4+x6

        3个3克砝码可以看成1+x3+x6+x9

        构造母函数

        g(x)=( 1+x1+x2+x3)( 1+x2+x4+x6)( 1+x3+x6+x9)

              =1+x+2x2+3x3+3x4+4x5+5x6+5x7+5x8+6x9+5x10+5x11+5x12+4x13+3x14+3x15+2x16+x17+x18

        可以看出，各项前的系数与表2中也是一一吻合的。 

        下面再看一道例题。

例2  掷骰子

        掷两只骰子（每只点数为1~6之一），可掷出的点数中，哪个点数的方案数最多？

        显然，两只骰子可掷出的点数最小为2（1+1），最多为12（6+6）。两只骰子的点数组合有6*6=36种，数据不大，可以枚举。例如：

        若两个骰子之和是2，只有1+1这1种可能。

         ……

        若两个骰子之和是6，有可能是1+5、5+1、2+4、4+2、3+3，一共5种可能。

        若两个骰子之和是7，有可能是1+6、6+1、2+5、5+2、3+4、4+3，一共6种可能。

         ……

        若两个骰子之和是12，只有6+6这1种可能。

        如果有m只骰子呢？显然不好列举。

        用母函数来解决。

         用（x+x2+…+x6）表示一只骰子的投掷过程，两只骰子的投掷可构造母函数

        G(x)= （x+x2+…+x6）（x+x2+…+x6）

                = x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12

        在母函数中，xn项前面的系数就表示了和为n的方案数目。

        如果骰子的数目为m，构造母函数为

        G(x)= （x+x2+…+x6）m  即可。 

        由上面两个例子我们可以看成，使用母函数来解决组合类计数问题时非常方便。通过构造母函数，我们得到幂级数形式的多项式，对于这个多项式我们不关心x的取值，也不关心其函数值，只需关心各项前的系数。

        母函数可分为很多种，包括普通母函数、指数母函数等。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视序列本身的特性和问题的类型。

        母函数有普通型的，也有指数型的。而我们通常在解题中碰到的大多是普通型的，指数型的较少。下面主要介绍普通型母函数的应用。

        采用母函数解决问题时，主要有两个关键问题要解决：（1）母函数的构造；（2）构造母函数时多项式相乘的实现。

        下面我们先讨论例1中母函数 g(x)=( 1+x1+x2+x3)( 1+x2+x4+x6)( 1+x3+x6+x9)的计算方法。

        由于母函数g(x)的最高幂次项为x18（3+6+9=18），可以定义两个数组C1[19]和C2[19]，其中数组C1保存多项式相乘后各项的系数，数组元素C1[i]保存xi的系数；C2用于中间运算。

        初始时，可以定义C1和C2的各元素初值均为0（除C1[0]=1外），表示初始时g(x)=1；也可以定义C1[0]=C1[1]=C1[2]=C1[3]=1，其余元素均为0，表示初始时g(x)= 1+x1+x2+x3，此时可以少进行一次多项式的相乘运算。

        为了加深对模板程序的编写方法的理解，我们采用g(x)=1时的定义来阐述。

        初始时，c1[0]=1，需进行三次相乘运算（可写成循环for (i=1;i