母函数

普通型母函数：
解决不重复的组合问题，整数拆分问题。
基本会构造多项式，然后利用一下多项式的乘法即可。多项式的系数即为方案数。
hdu1085
hdu1398[模板题]
hdu1171
hdu1709
hdu1028
hdu2069
hdu2152
(1) hdu1028[模板]:

#include <bits/stdc++.h>
using  namespace std;
int a[130],b[130];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++)
            a[i]=1;
        for(int i=2;i<=n;i++)//共n个多项式
        {
            memset(b,0,sizeof(b));//临时数组存系数,每次两个多项式项乘时，都要清空
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k<=n;k+=i)
                {
                    if(j+k>n)//只要计算幂<=n的项的系数即可
                        break;
                    b[j+k]+=a[j];
                }
            }
            for(int j=0;j<=n;j++)
                a[j]=b[j];
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

（2）hdu2069[对所有硬币的总数进行限制]
网上有很多答案是用dp写的，但用母函数也可以。
因为对硬币总个数有限制，所有不能按照一般的多项式相乘，每次相乘之前，要特判一下这个情况的硬币个数是否超出了限制（我用一个vector数组来保存）。
但一直WA，最后发现原因，当一种情况满足条件时，把它push到vector数组中，但这是这次相乘的结果，不能在这次用，否则会重复。

#include <bits/stdc++.h>
using namespace std;
int cent[7]={0,1,5,10,25,50};
int a[300],b[300];
vector<int>num[300];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++)
            num[i].clear();
        for(int i=1;i<=min(n,100);i++)
        {
            a[i]=1;
            num[i].push_back(i);
        }
        a[0]=1;
        for(int i=2;i<=5;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=1;k*cent[i]<=n;k++)
                {
                    if(j+k*cent[i]>n||k>100)
                        break;
                    if(j==0)
                    {
                        b[k*cent[i]]++;
                        num[k*cent[i]].push_back(k);
                        continue;
                    }
                    for(int w=0;w<num[j].size()&&w<a[j];w++)//wa点 &&w<a[j]
                    {
                        if(num[j][w]+k<=100)
                        {
                            b[j+k*cent[i]]++;
                            num[j+k*cent[i]].push_back(num[j][w]+k);
                        }
                    }
                }
            }
            for(int j=1;j<=n;j++)
            {
                a[j]+=b[j];
                b[j]=0;
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

指数型母函数：
可重集合的排列组合问题：
hdu1521:
[模板]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=15;
double a[maxn],b[maxn];
int fact[maxn];
int num[maxn];
void init()
{
    fact[0]=1;
    for(int i=1;i<maxn;i++)
        fact[i]=i*fact[i-1];
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        for(int i=0;i<=num[1];i++)//第一项初始赋值
            a[i]=1.0/fact[i];
        for(int i=2;i<=n;i++){//循环第2到第n项
            for(int j=0;j<=m;j++)
                for(int k=0;k<=num[i]&&k+j<=m;k++)
                b[k+j]+=a[j]/fact[k];
            for(int j=0;j<=m;j++){
                a[j]=b[j];
                b[j]=0;
            }
        }
        printf("%.0f\n",a[m]*fact[m]);
    }
}