母函数：所谓的母函数我觉得就是将一些组合数问题转化成多个多项式相乘，然后对系数做一些处理....
指数型母函数：这里讲的非常不错
泰勒公式：
e^x = 1 + x/1! + x^2/2! - x^3/3! + ... + x^n/n!;
e^-x = 1 - x/1! +x^2/2! - x^3/3! + ... +(-) x^n/n!;
关于母函数的题有HDU 1171，1398，1709，2065，2069，2082，2152；POJ 3046,3716,3734
1.hdu 1171
题目大意给出一个n，接下来n行每行有v, m两个数表示有m个值为n的数，将这两个数分成两堆让两堆的差值的绝对值最小，其实用背包就可以轻易的解决这个问题，我们用母函数的思想来做一下。
首先对每一组v,m 我们可以构造出形如这样的公式(x^v+x^2v+x^3v....x^mv)。这个公式的含义就是在m个v中选出一种，然后将所有公式相乘，枚举x幂数最接近sum/2的那一项。
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int maxa = 260000; int v[100], m[100]; bool a[2][maxa]; int main(){ int n; while(scanf("%d", &n)&&n >=0){ int sum = 0; for(int i = 0;i < n; i++){ scanf("%d%d", &v[i], &m[i]); sum += v[i] * m[i]; } memset(a, 0, sizeof(a)); a[0][0] = 1; for(int i =0 ;i < n; i++){ for(int k = sum/2; k >= 0; k--){ if(a[i%2][k]){ for(int j = 0; j <= m[i]; j++){ if(k+j*v[i] > sum/2)break; a[(i+1)%2][k+j*v[i]] = 1; } } } } for(int i = sum/2; i >= 0; i--){ if(a[n%2][i]){ printf("%d %d ", sum-i, i); break; } } } }
2.hdu 1398
题目大意就是用一些x^2的数相加能得到n，有多少种情况，思路同上。
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int maxa = 305; int a[maxa]; int main(){ int n; while(scanf("%d", &n), n){ for(int i = 0; i <= n; i++){ a[i] = 1; } for(int i = 2; i*i <= n; i++){ for(int k = n; k >= 0; k--){ for(int j = 1; k + j*i*i <= n; j++){ a[k+j*i*i] += a[k]; } } } printf("%d ", a[n]); } }
3.hdu 1709
给出一些和一个天平砝码，问这些砝码在[1,sum]之间不能称出的重量。
做到这的时候就感觉母函数难道就是背包吗...希望下面的题能给我惊喜....
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int maxa = 20005; bool w[maxa]; int a[105]; int main(){ int n; while(scanf("%d", &n) !=EOF){ int sum = 0; for(int i =0 ;i < n; i++){ scanf("%d", &a[i]); sum += a[i]; } memset(w, 0, sizeof(w)); w[10000] = 1; int zero = 10000; for(int i = 0; i< n; i++){ for(int k = zero + sum; k >= zero - sum; k --){ if(w[k]){ if(k+a[i] <= sum+zero) w[k+a[i]] = 1; } } for(int k = zero - sum; k <= zero +sum ; k++){ if(w[k]){ if(k - a[i] >= zero -sum) w[k-a[i]] = 1; } } } int ans = 0; for(int i =zero+1; i <= zero+sum; i++){ if(w[i] == 0) ans ++; } if(!ans)printf("0 "); else{ printf("%d ", ans); for(int i =zero+1 ;i <= zero+sum; i++){ if(!w[i]){ ans --; printf("%d", i-zero); if(ans !=0)printf(" "); } } puts(""); } } }
4.hdu 2065
题目大意：(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数%100
我们可以将这道题写成：(1+x/1!+x^2/2!+x^3/3!……)^2*(1+x^2/2!+x^4/4!+x^6/6!……)^2.这样的形式，题目就是要求出x^n/n!的系数
由泰勒公式(1+x/1!+x^2/2!+x^3/3!……)^2*(1+x^2/2!+x^4/4!+x^6/6!……)^2 = e^2x*1/4*(e^x+e^-x)^2=1/4(e^4x+1+2e^2x)，再将最后的公式做泰勒展开得到x^n/n!的系数为4^(n-1)+2^(n-1)
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; int quick(int x, long long n){ if(n == 0)return 1; int a = quick(x, n/2); a *= a; if(n & 1){ a *= x; } a %= 100; return a; } int main(){ int n; while(scanf("%d", &n), n){ long long x; for(int cas = 1; cas <= n; cas ++){ cin>>x; printf("Case %d: %d ",cas, (quick(4, x-1) + quick(2, x-1))%100); }puts(""); } }
5.hdu 2069
题目大意，有五种硬币组，给出一个数n问有多少种硬币数不超过一百的组成情况
很水的一道题但是自己蠢被卡了半天....
#include<stdio.h> #include<string.h> using namespace std; int a[5] = {1, 5, 10, 25, 50}; const int maxa = 300; int dp[maxa][maxa]; int main(){ int n; while(scanf("%d", &n)!=EOF){ memset(dp, 0, sizeof(dp)); for(int i = 0;i <= n; i++){ dp[i][i] = 1; } for(int i = 1; i <= 4; i++){ for(int k = n; k>= 0; k--){ for(int j = 1; k+j*a[i] <= n; j++){ for(int nn = 0; nn <=100; nn++) dp[k+j*a[i]][nn+j] += dp[k][nn]; } } } int ans = 0; for(int i = 0;i <= 100; i++){ ans += dp[n][i]; } printf("%d ", ans); } }
6.hdu 2082
又是个水题...连题意都懒得说...
#include<iostream> #include<string.h> #include<stdio.h> const int maxa = 55; int dp[maxa]; int a[maxa]; int main(){ int t; scanf("%d", &t); while(t--){ for(int i =0 ;i < 26; i++){ scanf("%d", &a[i]); } memset(dp, 0, sizeof(dp)); dp[0] =1 ; for(int i = 1; i <= 26; i++){ for(int k = 50; k >= 0; k--){ for(int j = k+i, h = 0; j <= 50 && h < a[i-1]; j+= i, h++){ //if(k == 0)printf("%d ", j); dp[j] += dp[k]; } } } int ans = 0; for(int i = 1;i <= 50; i++){ ans += dp[i]; } printf("%d ", ans); } }