普通型母函数、指数型母函数



前言

emmm争取在12点发出去！
母函数（生成函数），简直是解决组合问题的利器！
本文写的思路很短，而且无注释，是因为母函数入门就套公式嘛

  1. 普通型母函数
    http://www.wutianqi.com/?p=596
    https://wenku.baidu.com/view/10c0ddfb4693daef5ef73d77.html?from=search
  2. 指数型母函数
    http://www.wutianqi.com/?p=2644


硬币 - SZUCPC 2017 Winter


思路
校赛题目，忽然发现可以用母函数做！（当然啦正解用的是DP）
范围较大，注意优化

  #include <iostream>
  #include <cstdio>
  #include <algorithm>
  #include <cstring>
  #include <map>
  using namespace std;
  const int N = 1e6 + 15;

  int c1[N], c2[N];

  void solve(){
      int lim = 2;
      memset(c1, 0, sizeof(c1));
      memset(c2, 0, sizeof(c2));
      c1[0] = c1[1] = c1[2] = 1;

      for(int i = 2; i < N; i <<= 1){
          for(int k = 0; k <= (i << 1); k += i){
              for(int j = 0; j <= lim && j + k < N; j++){
                  c2[j + k] += c1[j];
              }
              lim += k;
          }
          for(int j = 0; j <= lim && j < N; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }
  }

  int main(){
      solve();
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          int n;
          scanf("%d", &n);
          printf("Case #%d: %d\n", csn++, c1[n]);
      }
  }


Square Coins - HDU 1398

题意
求由数1、4、9、…、17^2组成数n的方案数（每种数可以用无数次）
思路
同样是构造母函数（似乎也可以用背包做）

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 300 + 15;

  int c1[N], c2[N];

  void solve(){
      fill(c1, c1 + N, 1);
      memset(c2, 0, sizeof(c2));
      for(int i = 2; i <= 17; i++){
          for(int j = 0; j < N; j++){
              for(int k = 0; j + k < N; k += (i*i)){
                  c2[j + k] += c1[j];
              }
          }
          for(int j = 0; j < N; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }
  }

  int main(){
      solve();
      int n;
      while(scanf("%d", &n) && n){
          printf("%d\n", c1[n]);
      }
  }


Ignatius and the Princess III - HDU 1028

题意
问数n由数1、2、…、n组成的方案数（每种数都是无限的）
思路
已经懒得写思路了！
同上题

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 120 + 15;

  int c1[N], c2[N];

  void solve(){
      fill(c1, c1 + N, 1);
      memset(c2, 0, sizeof(c2));
      for(int i = 2; i < N; i++){
          for(int j = 0; j < N; j++){
              for(int k = 0; j + k < N; k += i){
                  c2[j + k] += c1[j];
              }
          }
          for(int j = 0; j < N; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }
  }

  int main(){
      solve();
      int n;
      while(~scanf("%d", &n)){
          printf("%d\n", c1[n]);
      }
  }


Holding Bin-Laden Captive! - HDU 1085

题意
给定1元、2元、5元硬币的数量，问最小的不能由他们凑出来的钱是几？
思路
首先构造母函数
构造完了之后计算，最后枚举第一个为0的位置，该位置即是最小的凑不出来的钱

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 8000 + 15;

  int c1[N], c2[N];

  int solve(int b[4]){
      int d[] = {0, 1, 2, 5};
      memset(c2, 0, sizeof(c2));
      memset(c1, 0, sizeof(c1));
      fill(c1, c1 + b[1] + 1, 1);

      for(int i = 2; i <= 3; i++){
          for(int j = 0; j < N; j++){
              for(int k = 0; k <= b[i]*d[i] && j + k < N; k += d[i]){
                  c2[j + k] += c1[j];
              }
          }
          for(int j = 0; j < N; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }

      for(int i = 1; i < N; i++){
          if(c1[i] == 0)  return i;
      }
      return -1;
  }

  int main(){
      int b[4];
      while(~scanf("%d%d%d", &b[1], &b[2], &b[3]) && b[1] + b[2] + b[3]){
          printf("%d\n", solve(b));
      }
  }


Big Event in HDU - HDU 1171

题意
给定n种物品的价值val[i]和数量cnt[i]，给出将他们尽量均分的方案
思路
首先可能能用背包做，当然这里用母函数做
构造完母函数计算完后，从(总价值+1)/2开始枚举，这样能尽量均分（或完全均分），第一个非0的位置就是均分方案

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 3e5 + 15;

  int c1[N], c2[N];

  void solve(int v[], int cnt[], int n, int& ans1, int& ans2){
      memset(c2, 0, sizeof(c2));
      memset(c1, 0, sizeof(c1));
      c1[0] = 1;
      int lim = 0;

      for(int i = 1; i <= n; i++){
          for(int k = 0; k <= cnt[i] * v[i]; k += v[i]){
              for(int j = 0; j <= lim && j + k < N; j++){
                  c2[j + k] += c1[j];
              }
          }
          lim += cnt[i] * v[i];
          for(int j = 0; j <= lim; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }

      int sum = 0;
      for(int i = 1; i <= n; i++){
          sum += v[i] * cnt[i];
      }
      for(int i = (sum + 1)/2; i < N; i++){
          if(c1[i]){
              ans1 = i;
              break;
          }
      }
      ans2 = sum - ans1;
  }

  int v[65], cnt[65];

  int main(){
      int n;
      while(~scanf("%d", &n) && n >= 0){
          for(int i = 1; i <= n; i++){
              scanf("%d%d", &v[i], &cnt[i]);
          }
          int ans1, ans2;
          solve(v, cnt, n, ans1, ans2);
          printf("%d %d\n", ans1, ans2);
      }
  }


排列组合 - HDU 1521


思路
指数型母函数模板题

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 20 + 15;

  int fac[N];
  int cnt[N];
  double c1[N], c2[N];

  void getFac(){
      fac[0] = 1;
      for(int i = 1; i < N; i++){
          fac[i] = fac[i - 1] * i;
      }
  }

  double solve(int n, int m){
      fill(c1, c1 + N, 0);
      fill(c2, c2 + N, 0);
      c1[0] = 1;

      for(int i = 1; i <= n; i++){
          for(int j = 0; j < N; j++){
              for(int k = 0; k <= cnt[i] && j + k < N; k++){
                  c2[j + k] += c1[j]/fac[k];
              }
          }
          for(int j = 0; j < N; j++){
              c1[j] = c2[j];
              c2[j] = 0;
          }
      }
      return c1[m] * fac[m];
  }

  int main(){
      getFac();
      int n, m;
      while(~scanf("%d%d", &n, &m)){
          for(int i = 1; i <= n; i++){
              scanf("%d", &cnt[i]);
          }
          printf("%.0f\n", solve(n, m));
      }
  }