首页 > 代码库 > 140804暑期培训.txt

140804暑期培训.txt

1、母函数
   母函数,顾名思义,就是母亲,那就说明,在这个函数里面还有儿子,即子函数。说白了,就是子函数可以看作是母函数的一个子集。
   而如何把这些子函数用一个母函数来表示呢?即所谓的通项公式。
   通俗理解为:母函数就是一个多项式前面的系数的一个整体的集合,而子函数就是这个多项式每一项前面的系数。
   母函数有普通型的,也有指数型的。而我们通常在做题当中碰到的大多是普通型的,指数型的较少,主要用来求解多重排列的题型
   普通型的可以用在求解组合以及整数拆分的题型中。

   例如,对于有n种物品,如果第i个物品有ki个,我们可以列式n个项相乘 (x^0+x^1+...x^k1)*(x^0+x^1+...x^k2)*...*(x^0+x^1+...x^kn)   ,每一项表示对于第i件物品,可以有(x^0+x^1+...x^ki)中取法,【注意系数都为1,因为同种物品去i件,它的取法是1】多项相乘:因为   取m件物品这件事实要分为对n种物品各取分别取1次【0~ki个】,  是组合计数的乘法原理, x^m 的系数是组合成m件物品的所有方案数。
  
    母函数的框架基本一样,

        如hdu1028,

         for(i=2;i<=n;i++)
         {
             for(j=0;j<=n;j++)
                for(k=0;k+j<=n;k+=i)//关键
                     b[k+j]+=a[j];
             for(j=0;j<=n;j++)
             {
                a[j]=b[j];
                b[j]=0;
             }
         }

注:根据题意,仔细分析,建立关系。