母函数总结

母函数总结

概述

母函数,又称生成函数,是ACM竞赛中经常使用的一种解题算法,常用来解决组合方面的题目。
母函数有两种,一种是指数型母函数一种是普通型母函数

普通型母函数

普通型母函数通常解决类似如下的问题:
给5张1元,4张2元,3张5元,要得到15元,有多少种组合?
某些时候会规定至少使用3张1元、1张2元、0张5元。
某些时候会规定有无数张1元、2元、5元。

普通型母函数有两种,一种是有限制的(硬币个数有限制的取),一种是无限制的(硬币个数无限的取)

普通型母函数的一般数学表示为:

有限制的:

/*
c1[i]:最后展开式的系数
num[i]:每种硬币的个数
v[i]:每种硬币的面值
*/
int c1[N],c2[N],num[N],v[N];
mem(c1,0);
c1[0]=1;
for(int i=1; i<=种类数; i++)
{
    mem(c2,0);
    for(int j=0; j<=num[i]; j++)
        for(int k=0; k+j*v[i]<=n; k++)
            c2[k+j*v[i]]+=c1[k];
    memcpy(c1,c2,sizeof(c2));
}

无限制的:

/*
c1[i]:最后展开式的系数
v[i]:每种硬币的面值
n:代表需要组合成的数(或者其他限制)
*/
int c1[N],c2[N],v[N],n;
mem(c1,0);
c1[0]=1;
for (int i=1; i<=种类数; i++)
{
    mem(c2,0);
    for (int j=0; j*v[i]<=n; j++) //循环每个因子的每一项
        for (int k=0; k+j*v[i]<=n; k++) //循环a的每个项
            c2[k+j*v[i]]+=c1[k];//把结果加到对应位
    memcpy(c1,c2,sizeof(c2));//b赋值给a
}

例题:

  1. HDU1028 Ignatius and the Princess III(整数划分,母函数模板题,无限制)

    整数划分问题,给你一个数n,让你求出这个数有几种不同的划分。每个数有无限个可以用.

/*
此处省略v[i],因为v[i]=i
*/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1000+7;

int c1[N],c2[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        mem(c1,0);
        c1[0]=1;
        for(int i=1; i<=n; i++)
        {
            mem(c2,0);
            for(int j=0; j*i<=n; j++)
                for(int k=0; k+j*i<=n; k++)
                    c2[k+j*i]+=c1[k];
            memcpy(c1,c2,sizeof(c2));
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}
  1. HDU1398 Square Coins(母函数,无限制的)

有面值为$1^2,2^2,3^2,…,17^2$的硬币无限个,然后给出一个n,问有多少种组成方法可以组成n.

const int N=1000+7;
int a[N],b[N];
int v[N];
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1; i<=17; i++)
            v[i]=i*i;
        mem(a,0);
        a[0]=1;
        for (int i=1; i<=17; i++)
        {
            mem(b,0);
            for (int j=0; j*v[i]<=n; j++) //循环每个因子的每一项
                for (int k=0; k+j*v[i]<=n; k++) //循环a的每个项
                    b[k+j*v[i]]+=a[k];//把结果加到对应位
            memcpy(a,b,sizeof(b));//b赋值给a
        }
        printf("%d\n",a[n]);
    }
    return 0;
}
  1. HDU1085 Holding Bin-Laden Captive!(母函数,有限制的)

现在有面值为1元,2元,5元的硬币若干枚,问这些硬币不能组成的最小金额是多少。

const int N=8000+7;
int c1[N],c2[N],num[N];
int v[4]= {0,1,2,5};
int main()
{
    int n;
    while(scanf("%d%d%d",&num[1],&num[2],&num[3])&&num[1]+num[2]+num[3])
    {
        int n=num[1]*1+num[2]*2+num[3]*5;
        mem(c1,0);
        c1[0]=1;
        for(int i=1; i<=3; i++)
        {
            mem(c2,0);
            for(int j=0; j<=num[i]; j++)
                for(int k=0; k+j*v[i]<=n; k++)
                    c2[k+j*v[i]]+=c1[k];
            memcpy(c1,c2,sizeof(c2));
        }
        int ans=0;
        while(c1[ans])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

优化版:

const int N=1000+7;
int w[4]= {0,1,2,5};
int n[4],a[8005],b[8005],ans,lst;
void init()
{
    mem(a,0);
    a[0]=1;
    lst=0;
    for(int k=1; k<=3; k++)
    {
        lst+=w[k-1]*n[k-1];//求出最高次数
        for(int i=0; i<=lst; i++)
            for(int j=0; j<=n[k]; j++)
                b[i+j*w[k]]+=a[i];
        memcpy(a,b,sizeof(a));
        mem(b,0);
    }
}

int main()
{
    while(scanf("%d%d%d",&n[1],&n[2],&n[3])&&n[1]+n[2]+n[3])
    {
        init();
        ans=0;
        while(a[ans])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

指数型母函数

关于指数型母函数:指数型母函数 简介

指数型母函数的一般问题为:

有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数

模板:

/*
N:范围
c1:最后系数的下标
num[i]:第i个物品的数量
A[i]:i的阶乘
*/
const int N=10+7;
double c1[N],c2[N],A[N];
int num[N];
void init()
{
    A[0]=A[1]=1;
    for(int i=2; i<=11; i++)
        A[i]=A[i-1]*i;
}
mem(c1,0);
c1[0]=1.0
      for(int i=1; i<=n; i++)
{
    mem(c2,0);
    for(int j=0; j<=num[i]; j++)
        for(int k=0; k+j<=m; k++)
            c2[k+j]+=c1[k]/A[j];
    memcpy(c1,c2,sizeof(c2));
}
double ans=c1[所求项]*A[所求项];

例题:

HDU1521 排列组合(指数型母函数,有限制的)

指数型母函数因为每种物品有数量,所以引入了阶乘,比如给出一组样例:

2 2
1 2

那么就应该:

(1+\frac{x^1}{1!})*(1+\frac{x^1}{1!}+\frac{x^2}{2!}) =1+2x+\frac{3}{2}x^2+\frac{1}{2}x^3

因为$x^2$项的系数为$\frac{3}{2}$,所以答案就是$\frac{3}{2}*2!=3$.

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=10+7;
double c1[N],c2[N],A[N];
int num[N];
void init()
{
    A[0]=A[1]=1;
    for(int i=2; i<=11; i++)
        A[i]=A[i-1]*i;
}
int main()
{
    init();
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1; i<=n; i++)
            scanf("%d",&num[i]);
        mem(c1,0);
        c1[0]=1.0;
        for(int i=1; i<=n; i++)
        {
            mem(c2,0);
            for(int j=0; j<=num[i]; j++)
                for(int k=0; k+j<=m; k++)
                    c2[k+j]+=c1[k]/A[j];
            memcpy(c1,c2,sizeof(c2));
        }
        double ans=c1[m]*A[m];
        printf("%.lf\n",ans);
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注