简单记录一波母函数的学习过程。

以题目HDU1085 Holding Bin-Laden Captive!为例：

题目大意如下：

有三种面值的硬币，面值分别为1、2、5；

现输入 num_1, num_2, num_5，分别表示三种面值的硬币的个数，

输入0 0 0表示输入结束；

输出ans，为这三种硬币所不能组合出的最小金额。

AC代码如下：

#include<iostream>
#include<string.h>
using namespace std;
int n[3], val[3] = { 1,2,5 }, c1[8005], c2[8005];
int main() 
{
    while (cin >> n[0] >> n[1] >> n[2] && (n[0] || n[1] || n[2]))
    {
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        c1[0] = 1;
        int max = 1 * n[0] + 2 * n[1] + 5 * n[2];
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j <= max; ++j)
                for (int k = 0; k <= val[i] * n[i]; k += val[i])
                    c2[j + k] += c1[j];
            for (int j = 0; j <= max; ++j)
                c1[j] = c2[j], c2[j] = 0;
        }
        int flag = 0;
		for (int i = 0; i <= max; ++i)
            if (!c1[i])
            {
                cout << i << endl;
                flag = 1;
                break;
            }
        if (!flag) cout << max + 1 << endl;
    }
    return 0;
}

分模块解释：

1. n[3]用于记录num_1,num_2,num_5, val[3]存储三种面额，方便后续遍历;
2. 由母函数公式，本题P(x) = (1+x+x^2+……+x^num_1)(1+x^2+x^4+……+x^(2*num_2))(1+x^3+x^9+……+x^(3*num_3))，c1数组的下标表示x的次方、值表示对应次方的x的系数，c2用于辅助计算。
3. 第一个for循环：表示下面操作的对象是P(x)的第 i 个多项式
4. 第二个for循环：用变量 j 遍历当前计算结果中x的每一次幂，比如j=0就是x^0，j=1就是x^1
5. 第三个for循环：遍历当前多项式中的每一项，即模拟x^k * x^j = x^(j+k)，然后将对应得到的系数与上一次计算的结果相加。
6. 循环后遍历c1数组，如果某一个下标对应的数组内的值为0，就说明相乘计算中未出现这一项，也就是无法组合得到该项，则将其作为结果输出，如果找不到这个值，则输出所能组合得到的最大面额+1.