首页 > 代码库 > 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;
}
}
注:根据题意,仔细分析,建立关系。