首页 > 代码库 > 算法总结之母函数

算法总结之母函数

1.概念

  生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多。形式上说,普通型生成函数用于解决多重集的组合问题,而指数型母函数用于解决多重集的排列问题。母函数还可以解决递归数列的通项问题(例如使用母函数解决斐波那契数列的通项公式)。

2.组合问题中的应用

  先放两句百度百科上的原话:

     1.“把组合问题的加法法则和幂级数的乘幂对应起来”

     2.“母函数的思想很简单 — 就是把离散数列和幂级数一 一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造. “

  再放两个可以用母函数解决的问题:

    问题1:有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?

    问题2:求用1分、2分、3分的邮票贴出不同数值的方案数(邮票个数没有限制)?

  从这两个问题可以看出来,用母函数是用来解决:

    有N种重量的物品,每种物品有M个(1-无穷),求可以组合出来的重量的个数和该重量的方案数。

  和背包问题分类类似,我们可以把这些问题分为:01(每个物品只有一件),完全(每个物品不限量),多重(每个物品都有指定的个数),混合。。

3.问题分析

  先来假设一个母函数:G(x)=a0*X^0+a1*X^1+a2*X^2+a3*X^3+...+an*X*n

  1)问题1:

    再假设一个函数:G(x)=(1+X^1)(1+X^2)(1+X^3)(1+X^4) 

      其中(1+X^1)可以看做是 (1*X^0+1*X^1)==>{不使用1克的砝码,使用1克的砝码}

      那么将多项式分解后:G(x)=1+X+X^2 +2*X^3 +2*X^4+2*X^5+2*X^6+2*X^7+X^8+X^9+X^10

      就将所有砝码使用与否的情况都考虑到了。

      这时,函数中的 2*X^3 就代表了 有两种方案可以组成3(3=3;3=1+2)..

      那么G(x)中系数不为零的X^P,代表P可以被组合出来,系数为可以组合的方案数。

  2)问题2:

    同假设一个函数:G(x)=(1+X^1+X^2+X^3+...)(1+X^2+X^4+X^6+...)....

    其中(1+X^2+X^4+X^6+...)可以看做{不使用1毛的邮票,使用1个1毛的邮票,使用2个1毛的邮票...}

    分解后类似于问题1中的G(x)=1+X+X^2 +2*X^3 +2*X^4+2*X^5+2*X^6+2*X^7+X^8+X^9+X^10 

    后函数中X的系数与指数与问题1中的所代表的相同。

  3)扩展:

    由问题2中的:其中(1+X^2+X^4+X^6+...)可以看做{不使用1毛的邮票,使用1个1毛的邮票,使用2个1毛的邮票...}

    可以推论:当重量为N的物品,有M个时,可以写成(1+X^N+X^2N+X^3N+...+X^MN)

3.代码实现

  转载自Tanky Woo博客

 1 #include <iostream> 2 using namespace std; 3 // Author: Tanky Woo 4 // www.wutianqi.com 5 const int _max = 10001;  6 // c1是保存各项质量砝码可以组合的数目 7 // c2是中间量,保存没一次的情况 8 int c1[_max], c2[_max];    9 int main()10 {    //int n,i,j,k;11     int nNum;   // 12     int i, j, k;13  14     while(cin >> nNum)15     {16         for(i=0; i<=nNum; ++i)   // ---- ①17         {18             c1[i] = 1;19             c2[i] = 0;20         }21         for(i=2; i<=nNum; ++i)   // ----- ②22         {23  24             for(j=0; j<=nNum; ++j)   // ----- ③25                 for(k=0; k+j<=nNum; k+=i)  // ---- ④26                 {27                     c2[j+k] += c1[j];28                 }29             for(j=0; j<=nNum; ++j)     // ---- ⑤30             {31                 c1[j] = c2[j];32                 c2[j] = 0;33             }34         }35         cout << c1[nNum] << endl;36     }37     return 0;38 }

 

4.代码详解

    我们需要把一个形如G(x)=(1+X^1+X^2+X^3+...)(1+X^2+X^4+X^6+...)....这样的函数

    转换成形如F(x)=1+X+X^2 +2*X^3 +2*X^4+2*X^5+2*X^6+2*X^7+X^8+X^9+X^10 的函数

    步骤如下:

      1)初始化F(x)= “G(x)的第一个括号中的内容” 代码中备注为

      2)将G(x)的第二个括号乘入F(x)中  代码中备注为

         (1)将F(x)中第一项与G(x)中第二个括号的每一项相乘 代码中备注为

         (2)将F(x)中第二项与G(x)中第二个括号的每一项相乘

         .....

      3)将G(x)的第三个括号乘入F(x)中

      4)将G(x)的第四个括号乘入F(x)中

      ...

    备注:

      1) C1[i]中存的是 X^i的系数,C2[]为临时数组,用来保证C1[]的正确性。

      2)根据题目给的物品重量的不同,初始化会不同,且后面的for()的累加也不同。

5.相关练习

    HDU1398 Square Coins

    HDU1028 Ignatius and the Princess III

    HDU1085 Holding Bin-Laden Captive!

    HDU1171 Big Event in HDU