这篇文章上次修改于 487 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记7——母函数

定义

母函数实际上就是一个多项式和其系数表达的关系，

对于多项式x2 + 2x + 1就是序列1 2 1的母函数

母函数的基础转化

问题

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

构造

对此我们可以构造母函数，对于每个砝码，我们让砝码的重量作为x的指数。

对于4g的砝码，我们可以设置为(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

对于ax^b也就代表对于b克物品有a种方案可以称出来

那么如何解释 (1 + x^4)的含义呢。

对于结果式(1 + x) (1 + x^2) (1 + x^3) (1 + x^4)结果的每一项，都是从这四项中二选一然后相乘得到的。(1 + x^4)也就意味着，要不我取用4g砝码，要不我就不取。

代码

这是一种基础的构造方式，把题目含义转化为多项式相乘，利用程序帮助计算

// 计算 (1 + x) (1 + x^2) (1 + x^3) (1 + x^4)
result[0] = 1; // 代表初始值 为 1 * x ^ 0 + 0 * x ^ 1 + 0 * x ^ 2 ....
for(int i = 1; i < 4; i++){ // 4为多项式的个数
    for(int j = 0; j <= 10; j++){  // 10为需要储存多项式结果次数的最大值
        temp[j + k] += result[j];
    }
    for (int j = 0; j <= score; j++)
    {
        result[j] = temp[j];
        temp[j] = 0;
    }
}
// result

母函数多项式内无限项

求用1分、2分、3分的邮票贴的某个数值的方案数—— 因邮票允许重复，故母函数为：

G(x) = (1 + x + x^2 + …) (1 + x^2 + x^4 + …) (1 + x^3 + x^6 + …)

由上题总结 对于结果ax^b也就代表对于b克物品有a种方案可以称出来

同样是获得结果多项式对应项的系数

多了无限项的条件，实际上我们计算的x次数只要不超过指定次数即可。例如我们求9以内的邮票的次数，x^4 与 x^6 我们就不用计算储存考虑

问题

整数拆分,就是把整数分解成若干整数的和，比如：3 = 1+1+1, 3 = 1+2 等等；整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。求整数n的拆分数。

构造

对于n来说相当于有1分、2分、3分… n分n种邮票贴出数值为n的方案数，只要构造

G(x) = (1 + x + x^2 + …) (1 + x^2 + x^4 + …) (1 + x^3 + x^6 + …) (1 + x^4 + x^8 + …)… (1 + x^n + x^2n + …)

并求结果即可，此时结果中大于n次的项都不需要计算。

代码

result[0] = 1;
for (i = 1; i <= n; i++) // 代表了n个多项式
{
    for (j = 0; j <= n; j++)
        for (k = 0; k + j <= n; k += i) // i为当前多项式的每项递增的次数
        {  // 当 k + j 比n大，不需要进行计算，高次数不会影响低次数
            temp[j + k] += result[j];
        }
    for (j = 0; j <= n; j++)
    {
        result[j] = temp[j];
        temp[j] = 0;
    }
}
cout << result[n] << endl;

母函数多项式无规律系数

对于自定义系数，理解上反而比无限项简单，对于价值为v的物品有n个其多项式就是

(1 + x^v + x^2v + … + x^nv)

或者是系数并不是简单递增，例如平方数等等

问题1

告诉各个物品的各个价格和数量，求他们组合成某个价值数的组合种类有几种。(限制了数量)

代码

// 结构体说明
srtuct Item{
    int value;
    int num;
}
// 结构体说明 items是该结构体vector
result[0] = 1;
for (Item it:items) // 代表了items.size()个多项式
{
    for (j = 0; j <= n; j++)
        for (k = 0; k * it.value + j <= n and k <= it.num; k ++) // 增加限制条件 k <= it.num
        {
            temp[k * it.value + j] += result[j];
        }
    for (j = 0; j <= n; j++)
    {
        result[j] = temp[j];
        temp[j] = 0;
    }
}
cout << result[n] << endl;

问题2

同样是硬币组合，现在硬币只有1,4,9,16等平方数的种类直到289，对于一个价值有几种组合。

代码

int coins = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289};
result[0] = 1;
for (int value:coins) // 代表了coins.size()个多项式
{
    for (j = 0; j <= n; j++)
        for (k = 0; k * value + j <= n; k ++)
        {
            temp[k * value + j] += result[j];
        }
    for (j = 0; j <= n; j++)
    {
        result[j] = temp[j];
        temp[j] = 0;
    }
}
cout << result[n] << endl;

母函数多项式负系数

问题

给你一个天平，告诉你有的砝码，求该天平无法称出的重量有哪些

构造

有意思的地方在于，天平两段都可以放置砝码，例如5,2实际上还可以称出3.

对于这种问题，实际上就是砝码之间可以相减，我们的砝码多了一种选择方式，原本的砝码是不取，取一个，取多个。现在的砝码多了一个减去的作用，该作用在多项式中便体现为负的系数，对于砝码重量为v，多项式为

(x^-v + 1 + x^v)

代码

// 结构体说明
srtuct Item{
    int value;
    int num;
}
// 结构体说明 items是该结构体vector
result[0] = 1;
for (Item it: Item) // 代表了n个多项式
{
    for (j = 0; j <= n; j++)
        for (k = -it.num; k * it.value + j <= n and k * it.value + j >= 0 and j <= it.num; k ++) // k + j 要大于等于 0
        {
            temp[k * it.value + j] += result[j];
        }
    for (j = 0; j <= n; j++)
    {
        result[j] = temp[j];
        temp[j] = 0;
    }
}
cout << result[n] << endl;

Mai Icy