母函数在ACM中也是容易出现的题目。这次专门写这一个专题，以题带讲，从简到难。
hdu1028题：题意是输入n，求其组合式子的个数；
例子：
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1
+ 1;
个数为5；
Sample Input
4 10 20
Sample Output
5 42 627
典型入门题：AC代码如下：初始化的时候有一个优化是网上其他代码所没有具备的。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int n; while(~scanf("%d",&n)) { int a[2][n+1]; memset(a,0,sizeof(a)); //这是一个优化 a[0][0] = a[1][0] = 1; for(int i=1;i<=n;++i) { memset(a[1],0,sizeof(a[1])); for(int j=0;j<=n;++j) for(int k=0;j+k<=n;k += i) a[1][k+j] += a[0][j]; memcpy(a[0],a[1],sizeof(a[0])); } printf("%d ",a[0][n]); } return 0; }
hdu1085：
题意：有1,2,5元，数量对应问n1,n2,n5;求最小不能组成。
AC代码：
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int n1,n2,n5; while(~scanf("%d%d%d",&n1,&n2,&n5)) { if(n1==0&&n2==0&&n5==0) break; int maxS = n1 + 2*n2 + 5*n5 + 1; int a[2][maxS+1]; memset(a,0,sizeof(a)); for(int i=0;i<=n1;++i) a[0][i] = 1; for(int i=0;i<=n1;++i) for(int j=0;j<=2*n2;j += 2) a[1][i+j] += a[0][i]; memcpy(a[0],a[1],sizeof(a[0])); memset(a[1],0,sizeof(a[1])); for(int i=0;i<=n1+2*n2;++i) for(int j=0;j<=5*n5;j += 5) a[1][i+j] += a[0][i]; for(int i=0;i<=maxS;++i) { if(a[1][i]==0) { printf("%d ",i); break; } } } return 0; }
hdu2082：
中文题不解释了，母函数，然后从1加到50就能AC了。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { __int64 f[2][51]; memset(f,0,sizeof(f)); f[0][0] = 1; int c; for(int i=1;i<=26;++i) { scanf("%d",&c); c = i*c; //把个数转换成价值限制 for(int j=0;j<=50;++j) for(int k=0;j+k<=50&&k<=c;k += i) f[1][j+k] += f[0][j]; memcpy(f[0],f[1],sizeof(f[1])); memset(f[1],0,sizeof(f[1])); } __int64 sum = 0; for(int i=1;i<=50;++i) sum += f[0][i]; printf("%I64d ",sum); } return 0; }
hdu2110:
输入n，之后n行有pi，mi，分别表示价值与个数。求总价值的三分之一有多少种分法，结果mod10000，如果不能分则输出sorry。
AC代码如下：
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int n; while(~scanf("%d",&n),n) { int pi[n],mi[n],T=0;//价值，数量 for(int i=0;i<n;++i) { scanf("%d%d",&pi[i],&mi[i]); T += pi[i]*mi[i]; } bool bCanDone = true; if(T%3 != 0) bCanDone = false; else{ int a[2][T+1]; memset(a,0,sizeof(a)); a[0][0] = a[1][0] = 1; for(int i=0;i<n;++i) { memset(a[1],0,sizeof(a[1])); for(int j=0;j<=T;++j) for(int k=0;k+j<=T&&k<=pi[i]*mi[i];k += pi[i]) a[1][k+j] = (a[1][k+j]+a[0][j])%10000; memcpy(a[0],a[1],sizeof(a[0])); } if(a[0][T/3]==0) bCanDone = false; else printf("%d ",a[0][T/3]); } if(!bCanDone) printf("sorry "); } return 0; }
hdu2152：
输入n，m，表示n种水果种数，现在需要一个有m个水果组成的水果拼盘。
以下n行输入a，b，表示水果拼盘对该水果个数的限制[a,b];
求有多少种拼法？
案例：
2 3 1 2 1 2 3 5 0 3 0 3 0 3
输出：
2
12
如果做完以上3题，再做该题的时候，会发现特别简单。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { int n,m;//总的种数，需要的个数。 while(~scanf("%d%d",&n,&m)) { int f[2][m+1]; memset(f,0,sizeof(f)); f[0][0] = f[1][0] = 1; for(int i=0;i<n;++i) { int a,b; //每种水果在[a,b]区间 scanf("%d%d",&a,&b); memset(f[1],0,sizeof(f[1])); for(int i=0;i<=m;++i) for(int j=a;j<=b&&i+j<=m;++j) f[1][i+j] += f[0][i]; memcpy(f[0],f[1],sizeof(f[0])); } printf("%d ",f[0][m]); } }
指数型母函数：
排列组合知识点：
假设有n个元素，其中a1，a2，····，an互不相同，进行全排列，可得n!个不同的排列。若其中某一元素a1重复了n1次，全排列出来必有重复元素，其中真正不同的排列数应为n!/n1!，即其重复度为n1!
同样理由a1重复了n1次，a2重复了n2次，····，ak重复了nk次，n1+n2+····+nk=n。对于这样的n个元素进行全排列，可得不同排列的个数实际上是n! / (n1!)(n2!)(n3!)..;
以下是指数型母函数原型：
以下是acm常用的公式：
举例：n1=3，n2=2，n3=3，则取8次后，根据函数的到 res = 1/（3！*2！*3！）,把最终答案为8！/res;
hdu1521：
n种东西里调m个排列，顺序有关系。之后n行表示每种东西个数ci；这道题目错的原因是进行double转换时，最后直接强制转换成int输出，会有误差，应该使用0.lf格式化输出。如果没用到double类型，则不需要这样。
测试数据个两组
2 2 1 1
2 1 1 1
输出：
2
2
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int n,m; //从n种类型选出m件物品。 while(~scanf("%d%d",&n,&m)) { double f[2][m+1]; double fk[m+1]; memset(f,0,sizeof(f)); fk[0]= 1; for(int i=1;i<=m;++i) { fk[i] = fk[i-1]/i; } f[0][0] = 1; double c; for(int i=0;i<n;++i) { scanf("%lf",&c); for(int j=0;j<=m;++j) for(int k=0;k<=c&&k+j<=m;++k) { f[1][j+k] += f[0][j]*fk[k]; } memcpy(f[0],f[1],sizeof(f[0])); memset(f[1],0,sizeof(f[1])); } //用浮点数会有误差，因此使用.0lf //进行浮点数计算后，再求整形是，用.0lf printf("%.0lf ",(f[0][m]/fk[m])); } return 0; }