===
Index
普通生成函数
对于一个序列 a = a[0], a[1],...,a[n-1], a的普通生成函数为
F(x) = a[0] + a[1] * x + a[2]*x^2 + ... + a[n-1] * x^n
a可以是又穷序列或无穷序列。
例如
序列 [1,2,3] 的生成函数为 1 + 2x + 3x^2
序列 [1,2,4,8...] 的生成函数为 1 + 2x + 4x^2 + 8x^3 + ...
加减运算
序列a,b的生成函数分别为 F(x), G(x)，则
F(x) +/ G(x) 是 序列 a + b 的生成函数
乘法运算(卷积)
F(x)G(x) 的卷积，例如 n = 3 时，x^3的系数为 a[0]b[3]+a[1]b[2]+a[2]b[1]+a[3]b[0]
F(x)G(x) 是序列 c[i] = a[0]b[i]+a[1]b[i-1]+...+a[i]b[0] 的生成函数
普通生成函数可以用来解决多重集组合数的问题。
问题
有n种物品，每种有a[i]个，问取m个物品的组合数。
多重集组合数
设第i种物品选b[i]个， 0<=b[i]<=a[i] 任一种满足b[0]+b[1]+...b[n]=m的选择方案数为1，则所有满足
b[0]+b[1]+...b[n]=m的方案数，即为答案。
构造普通生成函数
第i种物品的生成函数为 1+x+x^2+...+x^(a[i]) ，即求n个生成函数的乘积的x^m 的系数。
指数即物品个数，系数即组合数
购买水果方案数
有n种水果，每种水果选购个数在[a[i],b[i]]之间，问买m种水果有多少种购买方案
- 0 <= n, m <= 100
- 0 <= a[i] <= b[i]<=100
分析
构造生成函数 (x^a[0]+...+x^b[0])(x^a[1]+...+x^b[1])...(x^a[n-1]+...+x^b[n-1]) 求x^m的系数
int countWays(vector<int> &a, vector<int> &b, int m) {
int n = a.size();
if (n == 0) return 0;
vector<int> f(m + 1), g(m + 1);
for (int i = a[0]; i <= b[0] && i <= m; ++i)
f[i] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= m; ++j)
for (int k = a[i]; k <= b[i] && k + j <= m; ++k)
g[j + k] += f[j];
g.swap(f);
fill(g.begin(), g.end(), 0);
}
return f[m];
}
获得分数的方法数
有n种题目，第i种题目有count[i]道，每道题值 mark[i]分，求恰好得到m分的方法数。 答案模1e9+7。 同种类型题目无法区分。
- 1 <= m <= 1000
- 1 <= n <= 50
- 1 <= count[i], mark[i] <= 50
分析
构造生成函数(1+x^(mark[0])+...+x^(count[0]*mark[0]))...(1+x^(mark[n-1])+...+x^(count[n-1]*mark[n-1])), 求 x^m的系数。
int waysToReachTarget(int m, vector<vector<int>>& a) {
int n = a.size(), x = a[0][0], y = a[0][1], P = 1e9 + 7;
vector<int> f(m + 1), g(m + 1);
for (int i = 0, t = min(m, x * y); i <= t; i += y)
f[i] = 1;
for (int i = 1; i < n; ++i) {
x = a[i][0], y = a[i][1];
for (int j = 0; j <= m; ++j) {
for (int k = 0, t = min(x * y, m - j); k <= t; k += y)
g[k + j] = (g[k + j] + f[j]) % P;
}
g.swap(f);
fill(g.begin(), g.end(), 0);
}
return f[m];
}
满足质因数分解的方案数
任何一个正整数都可以唯一分解成p1^(e1)*p2^(e2)...*pk^(ek)的形式，其中 p1,…pk是质数。对于一个正整数m，定义
f(m)={p1,e1,p2,e2,...pk,ek}，给定2n个数，表示f(m)的集合，求有多少个整数m满足f(m)等于这个集合。模998244353。
- 1 <= n <= 2022
- 1 <= a[i] <= 1e6
分析
void ac_yyf() {
cin >> n;
int mx = 0;
map<int,int> mp;
for (int i = 0; i < 2*n; ++i
) {
cin >> x;
mx=max(mx,x);
mp[x]++;
}
sieve(mx);
vector<mint> f(n + 1, 0);
f[0] = 1;
mint t = comb.fact(n);
for (auto &[p, c]: mp) {
t = t*comb.invfac(c);
if (!st[p] && p != 1) {
for (int i = n - 1; i >= 0; --i) {
f[i + 1] += f[i] * c;
}
}
}
cout << t * f[n] << "\n";
}
指数生成函数
序列 a的指数生成函数为 a[0]+a[1]x/(1!)+a[2]x^2/(2!)+...+a[n]x^n/(n!)
例如 序列 [1,1,...]的生成函数为 1+x/(1!)+x^2/(2!)+...+x^n/(n!) 即指数函数 e^x
加减运算
序列a,b的生成函数分别为 F(x), G(x)，则
F(x) +/ G(x) 是 序列 a + b 的生成函数
乘法运算(卷积)
F(x)G(x) 是 序列 c[i] = C(i,0)a[0]b[i]+C(i,1)a[1]b[i-1]+...+C(i,i)a[i]b[0] 的生成函数
其中 C(n,k)是组合数。
指数生成函数可以用来解决多重集的排列数问题
问题
有n种物品，第i种物品有a[i]个，问取m个物品的排列数。
多重集的排列数
设第i种物品选b[i]个， 0<=b[i]<=a[i] 任一种满足b[0]+b[1]+...b[n]=m的排列方案数为m!/(b[1]...b[n]!)，则所有满足
b[0]+b[1]+...b[n]=m的排列数之和，即为答案。
构造指数生成函数
第1种物品生成函数为F(1) = 1+x/(1!)+x^2/(2!)+...+x^a[1]/(a[1]!)
第n种物品生成函数为F(n) = 1+x/(1!)+x^2/(2!)+...+x^a[n]/(a[n]!)
即 F(1)*F(2)...F(n),求 x^m / (m!) 的系数。
所有满足b[0]+b[1]+...b[n]=m 的项的系数之和，再乘以 m! 即答案。
排列组合
有n种物品，第i种物品有a[i]个，问取m个物品的排列数。
- 1 <= n, m <= 10
- 答案不会超过int
int calc(vector<int> &a, int m) {
int n = a.size();
vector<double> fac(m + 1, 1), f(m + 1), g(m + 1);
for (int i = 2; i <= m; ++i)
fac[i] = fac[i - 1] * i;
for (int i = 0; i <= a[0] && i <= m; ++i)
f[i] = 1.0 / fac[i];
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= m; ++j)
for (int k = 0; k <= a[i] && k + j <= m; ++k)
g[j + k] += f[j] / fac[k];
g.swap(f);
fill(g.begin(), g.end(), 0);
}
return (int)(f[m] * fac[m] + 0.5);
}
常见生成函数
