母函数

定义(摘自百度百科):

对于任意数列a0,a1,a2…an 即用如下方法与一个函数联系起来:

G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 +….+ a_nx^n

则称G(x)是数列的母函数。

这个母函数有啥用呢?

先看一一个简单的例子,假设你有一角钱,二角钱,三角钱,四角钱各一张。那么你要买一个5角钱的东西,不找零,有几种方式?

通过枚举,我们不难发现,其实有两种方式,一种是一张一角钱+一张四角钱,另一种是一张二角钱+一张三角钱。

下面给出一种奇妙的解题方式:

一角钱表示成1+x,二角钱表示成1+x^2,三角钱表示成1+x^3,四角钱表示成1+x^4

(1+x)(1+x^2)(1+x^3)(1+x^4),根据本人亲自手算,这个式子结果是:

1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}

仔細观察想x^4的系数,发现它是2。这个与我们枚举得到的结果是相同的。

其实,我们要求买一个n角钱的东西有几种付钱方式,直接可以看指数是n的数的系数就行。

那么回到定义上,(1+x)*(1+x^2)*(1+x^3)*(1+x^4)就是母函数的一种形式。

那么我们怎么用代码来写这个式子的每项系数呢?

我们以(1+x)*(1+x^2)*(1+x^3)*(1+x^4)为例:

首先我们开两个数组c1[maxn],c2[maxn];其中c1用来存最后每项的系数,c2是临时存每项的系数。

假如计算之后的结果是c1[2]=5,则表示x^2的系数是5.

要写这个式子的代码,动动膝盖骨也知道是需要用循环语句的。其实写代码的过程就是一个模拟手算的过程。

那我们数组开多大好呢?其实我们可以发现,这个式子中x最大的指数应该是1+2+3+4=10 。所以开20个足够了。

如果手算的话,第一步应该是(1+x)*(1+x^2)得到1+x+x^2+x^3

因此要有循环变量i,用来记录运算到第几个式子,可以发现它从2循环到4.

0

Leave a Reply

Your email address will not be published.