母函数题目小结
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
遇到一个问题，学习一下母函数。
这些题目用DP，递推都可以解决。
http://acm.hut.edu.cn/?p=277这里有篇讲解不错。
生成函数主要为两种，普通型以及指数型。
普通型的一般求解就是模拟多项式系数求解。
而指数型一般数量级很大，需要通过级数化简。比较坑，要有不错的高数功底。
HDU 1085 Holding Bin-Laden Captive!
http://acm.hdu.edu.cn/showproblem.php?pid=1085
有币值1，2，5的硬币若干，问你最少的不能组成的币值为多少。
(1+x+x^2+x^3……x^c1)*(1+x^2+x^4……x^2*c2)*(1+x^5+x^10……x^5*c3)
接下来就是求出每项的系数。模拟一下就行了，两项两项
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<cmath>#define LL long long#define MOD 29#define eps 1e-6#define N 100010#define zero(a) fabs(a)<epsusing namespace std;int val[5]={1,5,10,25,50};int c1[255][105]={0},c2[255][105]={0};int cnt[30];int main(){ for(int i=0;i<=100;i++) c1[i][i]=1; for(int i=1;i<5;i++){ for(int j=0;j<=250;j++) for(int k=0;k+j<=250;k+=val[i]) for(int r=0;r+k/val[i]<=100;r++) c2[j+k][r+k/val[i]]+=c1[j][r]; for(int j=0;j<=250;j++) for(int k=0;k<=100;k++){ c1[j][k]=c2[j][k]; c2[j][k]=0; } } int n; while(scanf("%d",&n)!=EOF){ int ans=0; for(int i=0;i<=100;i++) ans+=c1[n][i]; printf("%d\n",ans); } return 0;}HDU 1709 The Balance
http://acm.hdu.edu.cn/showproblem.php?pid=1709
杠杆问题，也就是因为有左右之分，价值有正负。为了避免下标出现负的，统一加上某个值，可以是价值总数。
HDU 2065 "红色病毒"问题
http://acm.hdu.edu.cn/showproblem.php?pid=2065
POJ 3734 Blocks
http://poj.org/problem?id=3734
这两题是指数型母函数，需要用到泰勒级数等数学知识。
详见这里http://blog.csdn.net/acm_cxlove/article/details/7831009