母函数及其应用

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

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

1．母函数的原理

        对于序列C₀、C₁、C₂、…、C_n，构造函数G(x)=C₀+C₁x+C₂x²+…+C_nxⁿ，称G(x)为序列C₀、C₁、C₂、…、C_n的母函数。

        先来看一道例题。

例1  砝码称重

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

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

表1  4个砝码称重

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

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

1个2克砝码可以看成1+x²

1个3克砝码可以看成1+x³

1个4克砝码可以看成1+x⁴

构造母函数g(x)=(1+x¹)(1+x²)(1+x³)(1+x⁴)

                         =1+x+x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹+x¹⁰

        在这个函数中，若指数表示可称出重量，系数表示方案数，则可以看出重量为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个砝码称重

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

        3个1克砝码可以看成1+x¹+x²+x³，1表示1个不取，x¹表示取1个，x²表示取2个，x³表示取3个，以下同理。

        3个2克砝码可以看成1+x²+x⁴+x⁶

        3个3克砝码可以看成1+x³+x⁶+x⁹

        构造母函数

        g(x)=( 1+x¹+x²+x³)( 1+x²+x⁴+x⁶)( 1+x³+x⁶+x⁹)

              =1+x+2x²+3x³+3x⁴+4x⁵+5x⁶+5x⁷+5x⁸+6x⁹+5x¹⁰+5x¹¹+5x¹²+4x¹³+3x¹⁴+3x¹⁵+2x¹⁶+x¹⁷+x¹⁸

        可以看出，各项前的系数与表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+x²+…+x⁶）表示一只骰子的投掷过程，两只骰子的投掷可构造母函数

        G(x)= （x+x²+…+x⁶）（x+x²+…+x⁶）

                = x²+2x³+3x⁴+4x⁵+5x⁶+6x⁷+5x⁸+4x⁹+3x¹⁰+2x¹¹+x¹²

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

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

        G(x)= （x+x²+…+x⁶）^m  即可。 

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

2．母函数的应用

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

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

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

        下面我们先讨论例1中母函数 g(x)=( 1+x¹+x²+x³)( 1+x²+x⁴+x⁶)( 1+x³+x⁶+x⁹)的计算方法。

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

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

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

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

        当i=1时，进行第1次相乘运算，每次运算将数组C1中的非零元素（即多项式中的有效项）与当前多项式相乘，结果暂存到数组C2的对应数组元素中。

         第1次相乘运算完成1*（1+x¹+x²+x³）。

        由于此时只有C1[0]=1，它要与多项式1+x¹+x²+x³中的4项分别相乘

        因此，C2[0+0]= C2[0+0]+C1[0]=1，C2[0+1]= C2[0+1]+C1[0]=1，

                   C2[0+2]= C2[0+2]+C1[0]=1，C2[0+3]= C2[0+3]+C1[0]=1。

        运算完成后，将数组C2的各元素值转存到数组C1中，且重新置数组C2的各元素值为0。

        此时，C1数组中保存的多项式为1+x¹+x²+x³

        当i=2时，进行第2次相乘运算，第2次相乘运算完成（1+x¹+x²+x³）*（1+x²+x⁴+x⁶）。

        由于此时，C1[0]=1，，它要与多项式1+x²+x⁴+x⁶中的4项分别相乘

        因此，C2[0+0]= C2[0+0]+C1[0]=1，C2[0+2]= C2[0+2]+C1[0]=1，

                  C2[0+4]= C2[0+4]+C1[0]=1，C2[0+6]= C2[0+6]+C1[0]=1。

        C1[1]=1，它也要与多项式1+x²+x⁴+x⁶中的4项分别相乘

        因此，C2[1+0]= C2[1+0]+C1[1]=1，C2[1+2]= C2[1+2]+C1[1]=1，

                   C2[1+4]= C2[1+4]+C1[1]=1，C2[1+6]= C2[1+6]+C1[1]=1。

        C1[2]=1，它也要与多项式1+x²+x⁴+x⁶中的4项分别相乘

        因此，C2[2+0]= C2[2+0]+C1[2]=2，C2[2+2]= C2[2+2]+C1[2]=2，

                   C2[2+4]= C2[2+4]+C1[2]=2，C2[2+6]= C2[2+6]+C1[2]=1。

        C1[3]=1，它也要与多项式1+x²+x⁴+x⁶中的4项分别相乘

        因此，C2[3+0]= C2[3+0]+C1[3]=2，C2[3+2]= C2[3+2]+C1[3]=2，

                   C2[3+4]= C2[3+4]+C1[3]=2，C2[3+6]= C2[3+6]+C1[3]=1。

        运算完成后，同样将数组C2的各元素值转存到数组C1中，且重新置数组C2的各元素值为0。

        此时，C1数组中保存的多项式为1+x+2x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹

        当i=3时，进行第3次相乘运算，第3次相乘运算完成（1+x+2x²+2x³+2x⁴+2x⁵+2x⁶+2x⁷+x⁸+x⁹）*（1+x³+x⁶+x⁹）。我们可以像上面一样进行运算，类似写40个赋值表达式即可。但我们不这样，而是将上面的运算用循环的方法写出来。

  for  (int j=0; j<=18; j++)

      if  (C1[j]!=0)       对多项式中的有效项进行乘法运算

      {

           for (int k=0;k<=3;k++)    // 当前有效项与多项式1+x³+x⁶+x⁹中每项相乘

               C2[k*i+j]=C2[k*i+j]+C1[j];

      }

  for (int j=0;j<=18;j++)

  {  c1[j]=c2[j];   c2[j]=0;  }

        按上面循环进行运算后，C1数组中保存的多项式为：

        1+x+2x²+3x³+3x⁴+4x⁵+5x⁶+5x⁷+5x⁸+6x⁹+5x¹⁰+5x¹¹+5x¹²+4x¹³+3x¹⁴+3x¹⁵+2x¹⁶+x¹⁷+x¹⁸

         这样，例1中的扩展问题我们可以写成如下的程序。

#include <stdio.h>

int main(void)

{

        int c1[19],c2[19];

        for (int i=0;i<19;i++)

         {

             c1[i]=c2[i]=0;

         }

         c1[0]=1;

         for (int i=1;i<=3;i++)

         {

                   for (int j=0;j<=18;j++)

                           if (c1[j])

                              for (int k=0; k<=3;k++)

                                     c2[j+k*i]+=c1[j];

                  for(int j=0;j<=18;j++)

                 {  c1[j]=c2[j]; c2[j]=0; }

       }

      for (int i=0;i<=18;i++)

         printf("%d  ",c1[i]);

      return 0;

}

       更一般的。例如，有n种物品，且第i个物品有ki个，现要在这n种物品中取出m件物品，求取法的方案总数。采用母函数时，可以列n个多项式相乘 (x^0+x^1+...x^k1)*(x^0+x^1+...x^k2)*…*(x^0+x^1+...x^kn)，第i个多项式表示对于第i件物品，可以有(x^0+x^1+...x^ki)中取法。将这些多项式相乘后，结果中x^m项的系数就是组合成m件物品的所有方案数。同样可以套用上面的程序。

 例3  正整数的拆分

问题描述

给定一个正整数N，可以将其拆分成若干个小于或等于N的正整数之和。例如，N=4是，存在5种拆分方法，列举如下：

  4 = 4;

  4 = 3 + 1;

  4 = 2 + 2;

  4 = 2 + 1 + 1;

  4 = 1 + 1 + 1 + 1;

注意：4 = 3 + 1和4 = 1 + 3是同一种拆分方法，不能重复计数。

输入格式

输入包括多个测试数据，每个测试数据为一个正整数N (1<=N<=120)。输入N=0作为结束。

输出格式

对每个测试数据，输出将其拆分的不同方案数。每个结果占1行。

输入样例

4

10

20

0

输出样例

5

42

627

        （1）编程思路。

        对于正整数N，其拆分式中可以包括1~N这N个数，这N个数最多取N个，可以重复取某个数。

        数字1最多可取N个，可以看成1+x¹+x²+x³+…+x^N，1表示1个不取，x¹表示取1个1，x²表示取2个1，x³表示取3个1，表示取N个1，以下同理。

        数字2可以看成1+x²+x⁴+x⁶+…+x^N/2

         ……

        数字N可以看成1+x¹。

        构造母函数

           g(x)=( 1+x¹+x²+x³+…)( 1+x²+x⁴+x⁶+…)( 1+x³+x⁶+x⁹+…)……（1+x¹）

        （2）源程序。

#include <stdio.h>

int main(void)

{

    int c1[121],c2[121];

    int n,i,j,k;

    while(scanf("%d",&n)!=EOF)

    {

          for (i=0;i<=n;i++)

           {

              c1[i]=c2[i]=0;

           }

           c1[0]=1;

           for (i=1;i<=n;i++)

           {

                  for (j=0;j<=n;j++)

               if (c1[j])

                           for (k=0; j+k*i<=n;k++)

                                 c2[j+k*i]+=c1[j];

            for (j=0;j<=n;j++)

            {  c1[j]=c2[j]; c2[j]=0; }

           }

           printf("%d\n",c1[n]);

       }

       return 0;

} 

例4  找单词（HDU 2082）

Problem Description

假设有x1个字母A， x2个字母B，..... ，x26个字母Z，同时假设字母A的价值为1，字母B的价值为2，.....，字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。（组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。

Input

输入首先是一个整数N，代表测试实例的个数。

然后包括N行数据，每行包括26个<=20的整数x1,x2,.....x26.

Output

对于每个测试实例，请输出能找到的总价值<=50的单词数，每个实例的输出占一行。

Sample Input

2

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output

7

379297

        （1）编程思路。

        本题同样采用母函数来解决。定义数组int a[27]，其中数组元素a[0]~a[25]分别保存字母A~Z可供选取的个数；定义数组int b[27]，其中数组元素b[0]~b[25]分别保存字母A~Z的价值，显然b[i]=i+1。

        构造母函数g(x)=(1+x^b[0]+x^2*b[0]+x^3*b[0]+…+x^a[0]*b[0])

                                  (1+x^b[1]+x^2*b[1]+x^3*b[1]+…+x^a[1]*b[1])

                               ……(1+x^b[25]+x^2*b[25]+x^3*b[25]+…+x^a[25]*b[25])

        运算时，只保留幂次不超过50的项的系数。最后将求得的x¹~x⁵⁰项的系数全部加起来就是问题的答案。

        （2）源程序。

#include <stdio.h>

int main()

{

    int a[27],b[27],c1[51],c2[51];

    int n,i,j,k,sum;

    scanf("%d",&n);

    while (n--)

    {

       sum=0;

       for (i=0;i<26;i++)

       {

           scanf("%d",&a[i]);

           b[i]=i+1;

       }

       for (i=0;i<=50;i++)

          c1[i]=c2[i]=0;

       c1[0]=1;

       for (i=0;i<26;i++)

       {

           for (j=0;j<=50;j++)

              if (c1[j])

                 for (k=0;k+j<=50&&k<=a[i]*b[i];k+=b[i])

                 {

                     c2[k+j]+=c1[j];

                 }

           for(j=0;j<=50;j++)

           {  c1[j]=c2[j]; c2[j]=0; }

       }

       for(i=1;i<=50;i++)

          sum+=c1[i];

        printf("%d\n",sum);

    }

      return 0;

} 

例5  Square Coins （HDU1398）

Problem Description

People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.

There are four combinations of coins to pay ten credits:

ten 1-credit coins,

one 4-credit coin and six 1-credit coins,

two 4-credit coins and two 1-credit coins, and

one 9-credit coin and one 1-credit coin.

Your mission is to count the number of ways to pay a given amount using coins of Silverland.

Input

The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output

For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Sample Input

2

10

30

0

Sample Output

1

4

27

        （1）编程思路。

        本题同样采用母函数来解决。由于可选数为1²~17²共17种数，因此

        构造母函数g(x)=(1+x¹+x^2*1+x^3*1+…) (1+x^1*2*2+x^2*2*2+x^3*2*2+…)…(1+x^1*17*17)

        运算时，只保留幂次不超过300的项的系数。

        （2）源程序。

#include <stdio.h>

int main(void)

{

    int c1[301],c2[301];

    int n,i,j,k;

    for (i=0;i<=300;i++)

    {

       c1[i]=c2[i]=0;

    }

    c1[0]=1;

    for (i=1;i<=17;i++)

    {

           for (j=0;j<=300;j++)

           if (c1[j])

                    for (k=0; j+k*i*i<=300;k++)

                          c2[j+k*i*i]+=c1[j];

        for (j=0;j<=300;j++)

        {  c1[j]=c2[j]; c2[j]=0; }

    }

    while(scanf("%d",&n)!=EOF && n!=0)

           printf("%d\n",c1[n]);

    return 0;

} 

例6  分硬币

问题描述

有面值分别为1~6的6种硬币。小明和小红收集了这样的硬币若干枚，现在他们要将这些硬币按价值平分。但他们发现有时没法平分。例如，现有面值为1的硬币1枚，面值为3的硬币1枚，面值为4的硬币2枚，这4枚硬币他们就无法平分。

输入格式

输入包括多组测试数据，每组数据占1行，有n1, n2, ..., n6共6个非负整数，其中ni表示面值为i的硬币的个数。每种硬币最多不超过20000枚。

输入数据以“0 0 0 0 0 0”作为结束。

输出格式

对每组测试数据，输出一行“Collection #k:”，其中k为测试数据组的序号；然后如果能平分，输出“Can be divided.”，否则输出“Can't be divided.”。每组输出后加1空行。

输入样例

1 0 1 2 0 0

1 0 0 0 1 1

0 0 0 0 0 0

输出样例

Collection #1:

Can't be divided.

 

Collection #2:

Can be divided. 

        （1）编程思路。

        有6种硬币，每种硬币的枚数保存到数组int a[7]中，其中a[i]保存面值为i的硬币的枚数。如果各硬币枚数的同时计算出这些硬币的总价值sum。如sum为奇数，显然不能平分；若为偶数，则构造母函数，若母函数中幂次为sum/2的项的系数不为0，可以平分，否则不能平分。

        构造母函数为G(x)=(1+x+x²+x³+…+x^a[1])(1+x²+x⁴+…+x^2∗a[2])…(1+x⁶+x¹²+…+x^6*a[6])

        由于题目中规定每种硬币最多不超过20000枚，但实际上1~6的最小公倍数为60，因此我们将每种硬币的个数对60取模，不影响判断结果，但可大大提高效率，避免大量重复计算。

        （2）源程序。

#include <stdio.h>

int main(void)

{

    int a[7];

    int c1[631],c2[631];

    int n=0,i,j,k;

    while (1)

    {

         int sum=0;

         for (i=1;i<=6;i++)

         {

             scanf("%d",&a[i]);

             a[i]=a[i]%60;

             sum+=i*a[i];

         }

         if (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]==0) break;

         printf("Collection #%d:\n",++n);

         if (sum%2!=0) printf("Can't be divided.\n\n");

         else

         {

             sum=sum/2;

             for (i=0;i<=sum;i++)

             {

                c1[i]=c2[i]=0;

             }

             c1[0]=1;

             for (i=1;i<=6;i++)

             {

                      for (j=0;j<=sum;j++)

                    if (c1[j])

                                   for (k=0; k<=a[i] && j+k*i<=sum; k++)

                                           c2[j+k*i]+=c1[j];

                 for (j=0;j<=sum;j++)

                 {  c1[j]=c2[j]; c2[j]=0; }

             }

             if (c1[sum]!=0) printf("Can be divided.\n\n");

             else   printf("Can't be divided.\n\n");

         }

    }

    return 0;

} 

例7  换硬币

问题描述

在一次促销活动中，你收到了一堆硬币，这些硬币有1分、5分、10分、25分和50分共5种。在结算聘请的促销员的报酬时你准备用这些硬币支付。

例如，要支付某促销员11分，你可以有如下4中支付方式：1个10分和1个1分，2个5分和1个1分，1个 5分和6个1分，11个1分。

设某促销员的报酬为N分，用这5种硬币进行支付的总方案数为多少？为避免一个促销员拿一把硬币的麻烦，支付时限定给某一个促销员的硬币总个数不能超过100个。

输入格式

输入包括多行，每行为一个正整数N（N≤250）。

输出格式

对每行的正整数N，输出采用5中硬币支付的方案数，每个输出结果占1行。

输入样例

11

26

输出样例

4

13

        （1）编程思路。

        本题是母函数的扩展应用。因为题目中要求支付时限定给某一个促销员的硬币总个数不能超过100个。因此在记录组成价值N的不同方案数时，需要同时记录所用到的总硬币个数。

        将一般使用时采用的一维数组定义为二维数组int c1[251][101]={0},c2[251][101]={0};，其中元素c1[i][j]表示用j枚硬币组成价值为i的方案数。

       （2）源程序。

#include <stdio.h>

int c1[251][101]={0},c2[251][101]={0};

// 元素c1[i][j]表示用j枚硬币组成价值为i的方案数

int main(void)

{

    int v[5]={1,5,10,25,50};

    int i,j,k,l;

    for (i=0;i<=100;i++)

       c1[i][i]=1;  // 全采用面值为1的硬币，i枚硬币组成价值为i的方案数为1

    for (i=1;i<=4;i++)

    {

          for (j=0;j<=250;j++)

         for (k=0;k+j<=250;k+=v[i])

             for (l=0;l+k/v[i]<=100;l++)

                c2[k+j][l+k/v[i]]+=c1[j][l];

       for (j=0;j<=250;j++)

         for (k=0;k<=100;k++)

         {

            c1[j][k]=c2[j][k];

            c2[j][k]=0;

         }

    }

    int n;

    while (scanf("%d",&n)!=EOF)

    {

        int sum=0;

        for (i=0;i<=100;i++)

            sum+=c1[n][i];

        printf("%d\n",sum);

    }

    return 0;

} 

例8   硬币凑数

问题描述

设有num1个1元硬币，num2个2元硬币，num5个5元硬币，问你用这些硬币不能凑出的最小面值是多少？（0不算）

输入格式

输入包括多组测试用例。每组测试用例包括3个正整数num1、num2和num5 (0<=num_i<=1000)。以输入0 0 0表示结束。

输出格式

输出不能凑出的最小值。

输入样例

1 1 3

0 0 0

输出样例

4

        （1）编程思路。

        因为硬币有1分、2分和5分三种情况，每种硬币有个数限制，因此构造母函数为：

        G(x)=(1+x+x²+x³+…+x^num1)(1+x²+x⁴+…+x^2∗num2)(1+x⁵+x¹⁰+…+x^5∗num5)

        将母函数多项式展开后，xⁱ项对应的系数就是组成面值为i的方案数。

        然后从i=1开始遍历xⁱ项对应的系数，若某项xⁱ的系数为0，则i就是不能凑出的最小值。

        （2）源程序。

#include <stdio.h>

int main(void)

{

    int num[4],money[5]={0,1,2,5},c[8005];

    while(scanf("%d%d%d",&num[1],&num[2],&num[3])!=EOF)

       {

              if(num[1]==0 && num[2]==0 && num[3]==0)

                     break;

              int maxVal=0,i,j,k;

              for (i=0;i<8002;i++)

                     c[i]=0;

              c[0]=1;

              for (i=1;i<=3;i++)

              {

                     maxVal+=num[i]*money[i];

                     for (j=0;j<=maxVal;j++)

                            for (k=0;k<=num[i] && j+k*money[i]<=maxVal;k++)

                                   c[j+k*money[i]]+=c[j];

              }

              for (i=1;;i++)

                     if(c[i]==0)

                     {

                            printf("%d\n",i);

                            break;

                     }

       }

       return 0;

} 

例9  水果拼盘

问题描述

果农老根一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。由于今年收成很好，老根获得了大丰收。于是，很多人慕名而来，找老根买水果。

老根决定推出水果拼盘。每份水果拼盘由M个水果组成，拼盘中的每种水果，个数上有限制，既不能少于某个特定值，也不能大于某个特定值。

问老根一共可以推出多少种不同组合方案的水果拼盘？

注意：水果是以个为基本单位，不能够再分。对于两种方案，如果各种水果的数目都相同，则认为这两种方案是相同的。

输入格式

本题目包含多组测试，请处理到文件结束(EOF)。

每组测试第一行包括两个正整数N和M（0<N,M<=100）

接下来有N行水果的信息，每行两个整数A，B(0<=A<=B<=100)，表示至少要买该水果A个，至多只能买该水果B个。

输出格式

对于每组测试，在一行里输出总共能够卖的方案数。

题目数据保证这个答案小于10^9

输入样例

2 3

1 2

1 2

3 5

0 3

0 3

0 3

输出样例

2

12

        （1）编程思路。

        本题同样采用母函数来解决。定义数组int a[101]和int b[101]，其中数组元素a[i]和b[i]分别保存第i种水果在拼盘中的最少数目和最多数目。

        构造母函数g(x)=(x^a[1]+x^a[1]+1+x^a[1]+2+…+x^b[1]) (x^a[2]+x^a[2]+1+x^a[2]+2+…+x^b[2])

                                 ……(x^a[n]+x^a[n]+1+x^a[n]+2+…+x^b[n])

        运算时，只保留幂次不超过M的项的系数。

        （2）源程序。

#include <stdio.h>

int main(void)

{

    int c1[101],c2[101];

    int a[101],b[101];

    int n,m,i,j,k;

    while (scanf("%d%d",&n,&m)!=EOF)

    {

         for (i=1;i<=n;i++)

            scanf("%d%d",&a[i],&b[i]);

         for (i=0;i<=m;i++)

         {

             c1[i]=c2[i]=0;

         }

         c1[0]=1;

         for (i=1;i<=n;i++)

         {

                for (j=0;j<=m;j++)

               if (c1[j])

                         for (k=a[i]; k<=b[i] && j+k<=m; k++)

                               c2[j+k]+=c1[j];

             for (j=0;j<=m;j++)

             {  c1[j]=c2[j]; c2[j]=0; }

         }

           printf("%d\n",c1[m]);

    }

    return 0;

} 

例10  质数和分解

        选自洛谷题库（https://www.luogu.com.cn/problem/P2563）

题目描述

任何大于 1 的自然数 n 都可以写成若干个大于等于 2 且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，9 的质数和表达式就有四种本质不同的形式：

9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数 n(2 < n < 200) 。

输出格式

依次输出每一个自然数 n 的本质不同的质数和表达式的数目。

输入样例

2

200

输出样例

1

9845164

        （1）编程思路。

        先将200以内的所有质数求出来，保存到数组prime中。然后用数组中每个质数的取法作为一个多项式构造母函数。

        构造的母函数为g(x)=(1+x²+x⁴+x⁶+…) (1+x³+x^2*3+x^3*3+…) (1+x⁵+x^2*5+x^3*5+…)

                                       ……(1+x¹⁹⁹+x^2*199+x^3*199+…)

        且求得的母函数中最高幂次项的幂次不超过200.

        （2）源程序。

#include <stdio.h>

int isPrime(int n)

{

    if (n<2) return 0;

    for (int i=2;i<=n/2;i++)

        if (n%i==0) return 0;

    return 1;

}

int main(void)

{

       int prime[201],c1[201],c2[201];

       int i,j,k;

       int cnt=0;

       for (i=0;i<201;i++)

       {

           c1[i]=c2[i]=0;

           if (isPrime(i)==1) prime[cnt++]=i;

       }

       c1[0]=1;

       for (i=0;i<cnt;i++)

       {

              for (j=0;j<=200;j++)

                    if (c1[j])

                       for (k=0; j+k*prime[i]<=200;k++)

                            c2[j+k*prime[i]]+=c1[j];

             for(j=0;j<=200;j++)

            {  c1[j]=c2[j]; c2[j]=0; }

       }

      int n;

      while(scanf("%d",&n)!=EOF)

         printf("%d\n",c1[n]);

     return 0;

}

         在理解了母函数及其应用方法的基础上，可以刷一下如下的OJ题目。这几道题目均可以采用普通型母函数解决。

（1）Big Event in HDU  （http://acm.hdu.edu.cn/showproblem.php?pid=1171）

（2）Crisis of HDU （http://acm.hdu.edu.cn/showproblem.php?pid=2110）

（3）悼念512汶川大地震遇难同胞——来生一起走

（http://acm.hdu.edu.cn/showproblem.php?pid=2189）

（4）小A点菜     （https://www.luogu.com.cn/problem/P1164）

（5）砝码称重      （https://www.luogu.com.cn/problem/P2347）

（5）Ant Counting   （http://poj.org/problem?id=3046）

（6）Dollar Dayz    （http://poj.org/problem?id=3181）