WIKI

生成函数

从1，2，3，4取出一个或多个相加

能组合成几个数，每个数有几种组合
$$ (1+x)(1+x^2)(1+x^3)(1+x^4)=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} $$
那么就是

可以发现每一项系数与对应的组合数量都是相同的

生成函数的原理

将组合问题的加法与幂级数的乘幂对应起来

生成函数

对于序列h0,h1,h2,…… 构造函数 $g(x)=h_0+h_1x^1+h_2x^2\dots$

称$g(x)$ 为 系列 h的生成函数

Problem - 1028 (hdu.edu.cn)

code

#include <iostream>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
const int N = 201;
int c1[N], c2[N];
void init(int n) {
  for (int i = 0; i < n; i++) c1[i] = 1, c2[i] = 0;
  for (int k = 2; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j + i < n; j += k) {
        c2[i + j] += c1[i];
      }
    }
    for (int i = 0; i < n; i++) {
      c1[i] = c2[i];
      c2[i] = 0;
    }
  }
}
void solve() {
  while (cin >> n) cout << c1[n] << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  init(N);
  solve();
  return 0;
}

指数型母函数

可以用于求 排列数

假设有两个A 三个B 一个C

求排列数
$$ \begin{align} g(x)&=(1+\frac x{1!}+\frac {x^2} {2!})(1+\frac x{1!}+\frac {x^2} {2!}+\frac {x^3} {3!})(1+\frac x{1!})\\ &=1+3x+4x^2+\frac {19} 6x^3+\frac {19 }{12}x^4+\frac 1 2x^5+\frac 1 {12}x^6\\ &=1+\frac {3x}{1!}+\frac{8x^2}{2!}+\frac{19x^3}{3!}+\frac{38x^4}{4!}+\frac{60x^5}{5!}+\frac{60x^6}{6!} \end{align} $$
namo