母函数总结
概述
母函数，又称生成函数，是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
}
例题:
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;
}
有面值为的硬币无限个，然后给出一个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元，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[所求项];
例题:
指数型母函数因为每种物品有数量，所以引入了阶乘，比如给出一组样例:
2 2
1 2
那么就应该： 因为项的系数为，所以答案就是.
代码
#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;
}