母函数（整数划分）

母函数的分析

母函数的原理数，后生之辈没啥可讲的。完全可以站在巨人的肩膀上。下面给出杭电科技大学的课程链接，不懂得就自己去获取基础知识点吧。Click Here~

个人学了一些有关母函数的知识，经过本人的总结。个人觉得大体上解体策略可以分为动态规划及递归型和母函数求解型。而其中动态规划及递归的主要是运用与有关整数划分的问题。而整数划分又分很多种情况。下面给出哈工大学大牛写的博客链接自己可以去看看Click Here~，而母函数的问题就是上面给出的杭大的链接。下面就给出每种情况的问题详解吧。

而使用模板的时候还要注意题目的限定条件。如果，题目是要求把一个数或物品必须分成k份，则此时就要用到dp思想的运用。即，dp[k][n] = dp[k][n-k] + dp[k-1][n-1] (n>=k)。而当题目中说明可以把一个数或者物品分成任意的份数，则此事可以用到递归的模板。

整数划分模板：

typedef long long LL;
LL GetPartitation(int n,int m) //n表示要划分的整数，m表示序列中最大不大于m
{
    if(n==0||m==0||n==1||m==1) //根据题目变化，自己灵活设置
      return 1;
    else if(n < m)
      return GetPartitation(n,n);
    else if(n == m)
      return GetPartitation(n,n-1) + 1;
    else
      return GetPartitation(n,m-1) + GetPartitation(n-m,m);
}

我在根据本人自己对上面模板的理解告诉大家吧！我感觉这种方式比网上解释的更容易记忆。

if(n==0||m==0||n==1||m==1) //根据题目变化，自己灵活设置

return 1;

else if(n < m)//这个是显然的序列中最大的，肯定是不可能大于n的

return GetPartitation(n,n);

else if(n == m)//当序列中最大数是n==m时候，显然此时只可能只有一个n，然后递归比m小下一个数

return GetPartitation(n,n-1) + 1;

else//其中前部分是表示递归比m小的下一个数，后面一部份是表示可以与m组合成n的组合数有几个

return GetPartitation(n,m-1) + GetPartitation(n-m,m);

动态规划DP模版：

for(int i = 1;i < N;++i)  //初始化
   dp[1][i] = dp[i][i] = dp[0][i] = 1;
for(int i = 2;i < N;++i)  
  for(int j = i+1;j < N;++j){  //自己看上面哈工大链接的解释
     dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
  }

整数的划分在北大上有两题简单的入门题，

一题是放苹果题（运用上面的递归模板就可以解决）

二是Click Here~（是动态规划思想解决的问题）是整数划分中的第二类，即划分n是数量固定的k个数。

转移方程式：

dp[k][n] = dp[k][n-k] + dp[k-1][n-1];

母函数的模板：

流行版：

for(i = 0;i <= n;++i){
    c1[i] = 1; c2[i] = 0;
} 
for(i = 2;i <= n;++i){      //有多少个可以组合的数据种类
   for(j = 0;j <= P;++j){   //前一个括号中有多少项
      for(k = 0;k+j <= P;k += i){  //当前的括号数的指数最大可以达到的数值
         c2[k+j] += c1[j];
      }        
    }
    for(j = 0;j <= n;++j){  
       c1[j] = c2[j];  
       c2[j] = 0; 
    }
}
/* P为数据中可能的最大指数
   k+j<=P最大指数不超P
*/

改版版：

a[MAX],b[MAX];     //a为结果，b为中间结果
memset(a,0,sizeof(a));
a[0] = 1;
for(i = 1;i <= N;++i){
  memset(b,0,sizeof(b));
  for(j = min[i];(j<=max[i])&&j*v[i]<=P;++j){ //循环每个因子里的每一项
     for(k = 0;k+j*v[i]<=P;++k){              //循环a的每一个项
        b[k+j] += a[k];
     }
  }
  memcpy(a,b,sizeof(b));                   //b赋值给a
}

/*一、P是可能的最大指数。
  二、如果max是无穷，那么第二层循环条件j <= max[i]可以省掉
*/

函数模板的应用：(Click Here~)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 300+5;
int c1[N],c2[N];
int main()
{
    int n,i,j,k;
    while(cin>>n,n)
    {
        for(i = 0;i <= n;++i){
           c1[i] = 1;
           c2[i] = 0;
        }
        for(i = 2;i <= 17;++i){   //这里改变了一点  
            for(j = 0;j <= n;++j){   
               for(k = 0;k+j <= n;k += i*i){  //这里要根据题目要求变
                  c2[k+j] += c1[j];
               }
            }
            for(j = 0;j <= n;++j){
               c1[j] = c2[j];
               c2[j] = 0;
            }
        }
        cout<<c1[n]<<endl;
    }
    return 0;
}

对母函数的本质理解Click Here~

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e6 + 5;
int c1[N],c2[N];
int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k),(n||m||k))
    {
        int sum = n + 2*m + 5*k;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(int i = 0;i <= n;++i){ //1 coin
          c1[i] = 1;
        }
        for(int i = 0;i <= n;++i){   //2 coin
          for(int j = 0;j <= 2*m;j += 2){
             c2[i+j] += c1[i];
          }
        }
        for(int i = 0;i <= sum;++i){
           c1[i] = c2[i];
           c2[i] = 0;
        }
        for(int i = 0;i <= n+2*m;++i){ //5 coin
          for(int j = 0;j <= 5*k;j += 5){
             c2[i+j] += c1[i];
          }
        }
        for(int i = 0;i <= sum;++i){
           c1[i] = c2[i];
           c2[i] = 0;
        }
        int i;
        for(i = 0;i <= sum;++i){
           if(!c1[i]){
              printf("%d\n",i);
              break;
           }
        }
        if(i == sum+1){
           printf("%d\n",sum+1);
        }
    }
    return 0;
}

题目链接：Big Event In HDU

题意分析：

给你N个不同价值，不同数量的东西。叫你找出使这些物品可以达到最大的平均值。

思路分析：

原先我开始做的时候是用了一个结构体保存数据，然后给价值排序，但是后来TEL了。后来我看了别人的代码发现都不用排序。不知道为什么。其实，这道题可以用背包来做，我很早就见过，但是当时没做出来，最近在学母函数，于是就把它A了。就是一个简单的母函数模板题。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e6 + 5;
int c1[N],c2[N],val[N],num[N];
int main()
{
    int n,i,j,k;
    while(scanf("%d",&n),(n>=0))
    {
//        int sum = 0;
        for(i = 1;i <= n;++i){
           scanf("%d%d",&val[i],&num[i]);
//           sum += val[i]*num[i];
        }
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(i = 0;i <= val[1]*num[1];i += val[1]){
           c1[i] = 1;
        }
        int m = val[1]*num[1];
        for(i = 2;i <= n;++i){
          for(j = 0;j <= m;++j){
             for(k = 0;k <= val[i]*num[i];k += val[i]){
                c2[k+j] += c1[j];
             }
          }
          m += val[i]*num[i];
          for(j = 0;j <= m;++j){
             c1[j] = c2[j];
             c2[j] = 0;
          }
        }
        int mid = m/2;
        while(!c1[mid]) mid++;
        int two = m - mid;
        if(two > mid) swap(two,mid);
        printf("%d %d\n",mid,two);
    }
    return 0;
}

具有上下界的母函数：Click Here~

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e3 + 5;
int c1[N],c2[N],n1[N],n2[N];
int main()
{
    int n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i = 0;i < n;++i)
          scanf("%d%d",&n1[i],&n2[i]);
        memset(c1,0,sizeof(c1));
        for(i = n1[0];i <= n2[0];++i){
           c1[i] = 1;
        }
        for(i = 1;i < n;++i){
          memset(c2,0,sizeof(c2));
          for(j = 0;j <= m;++j){
             for(k = n1[i];k <= n2[i];++k){
                c2[j+k] += c1[j];
             }
          }
          memcpy(c1,c2,sizeof(c2));
        }
        printf("%d\n",c1[m]);
    }
    return 0;
}

题目链接：Click Here~

题目分析：

给你字母数量从A ~ B的个数，要求你求出在这些给出的字母个数中可以得到的组合数的总和不小于50的个数。昨天，就看到这题了，一开始居然没想明白，好吧，我承认，我SB了。经过多次的看题后才发现了，就是一个母函数的模板题。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100;
const int P = 50;
int c1[N],c2[N],a[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(c1,0,sizeof(c1));
        for(int i= 1;i <= 26;i++)
          scanf("%d",&a[i]);
        for(int i = 0;i <= a[1];++i){
           c1[i] = 1;
        }
        for(int i = 2;i <= 26;++i){
           memset(c2,0,sizeof(c2));
           for(int j = 0;j <= P;++j){
             for(int k = 0;(k+j<=P)&&(k <= a[i]*i);k += i){
                c2[k+j] += c1[j];
             }
           }
           memcpy(c1,c2,sizeof(c2));
        }
        int ans = 0;
        for(int i = 1;i <= P;++i){
           ans += c1[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}