大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
生成函数(母函数)
什么是生成函数：wiki上的介绍
在数学中，某个序列 ( a n ) n ∈ N \large {\displaystyle (a_{n})_{n\in \mathbb {N} }} (an)n∈N 的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。
母函数，又称生成函数，是ACM竞赛中经常使用的一种解题算法，常用来解决组合方面的题目。
生成函数的定义： g ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + . . . \large g(x)=a_0+a_1x+a_2x^2+a_3x^3+… g(x)=a0+a1x+a2x2+a3x3+…称 g ( x ) \large g(x) g(x)是序列 a 0 , a 1 , a 2 , . . . a_0,a_1,a_2,… a0,a1,a2,…的生成函数， x x x充当形式参数没有意义。
小题
一、
有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
我们用母函数来解决这个问题
1个1克砝码可以看成1+x^1,1表示不取，x^1表示取一个，以下同理
1个2克砝码可以看成1+x^2
1个3克砝码可以看成1+x^3
1个4克砝码可以看成1+x^4
那么生成函数就是
g ( x ) = ( 1 + x 1 ) ( 1 + x 2 ) ( 1 + x 3 ) ( 1 + x 4 ) = 1 + x + x 2 + 2 x 3 + 2 x 4 + 2 x 5 + 2 x 6 + 2 x 7 + x 8 + x 9 + x 10 \large g(x)=(1+x^1)(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} g(x)=(1+x1)(1+x2)(1+x3)(1+x4)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10
这个函数中可以看出重量为3克的方案有两种，重量为7的方案有两种，重量为10的有1种。
不难发现指数表示重量，系数表示方案数。
二、
求用1分、2分、3分的邮票贴出不同数值的方案数：
大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。
那么生成函数就是 g ( x ) = ( 1 + x + x 2 + x 3 + . . . ) ( 1 + x 2 + x 4 + x 6 + . . . ) ( 1 + x 3 + x 6 + x 9 + . . . ) \large g(x)=(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)(1+x^3+x^6+x^9+…) g(x)=(1+x+x2+x3+…)(1+x2+x4+x6+…)(1+x3+x6+x9+…)
以展开后的x^4为例，其系数为4，即4拆分成1、2、3之和的拆分方案数为4；
即 ：4=1+1+1+1=1+1+2=1+3=2+2
三、
设有n个标志为1,2,…,n的网袋，第i个(i=1,2,…n)网袋里放有ni个球。不同网袋里的球是不同的，而同一网袋里的球则是没有差别的，认为是相同的。询问从中取r个球的方案数。
设生成函数 g ( x ) = ( 1 + x 1 + x 2 + . . . + x n 1 ) ( 1 + x 1 + x 2 + . . . + x n 2 ) . . . \large g(x)=(1+x^1+x^2+…+x^{n1})(1+x^1+x^2+…+x^{n2})… g(x)=(1+x1+x2+…+xn1)(1+x1+x2+…+xn2)…
最后指数为r的那一项的系数就是方案数。
总结一下，生成函数大多用来解决有限或无限物体的组合方案。
给出通用模板，其实就是暴力拆这个函数罢了。
#include<cstdio>
using namespace std;
int N,g[2][125];
int main(){
while(~scanf("%d",&N)){
for(int i=0;i<=N;++i) g[1][i]=1,g[0][i]=0;
for(int i=2;i<=N;++i){
for(int j=0;j<=N;++j)
for(int k=0;k<=N-j;k+=i) g[i&1][j+k]+=g[1-(i&1)][j];
for(int j=0;j<=N;++j) g[1-(i&1)][j]=0;
}
printf("%d\n",g[N&1][N]);
}
return 0;
}
以上是一些基础，接下来给一道难题（反正我一点也不会，逃）：BZOJ4001
不会也没有关系，我们慢慢来。
特殊情况
当 a = { 1 , 1 , 1 , 1 , . . . } a=\{1,1,1,1,…\} a={
1,1,1,1,…}时 f ( x ) = 1 + x + x 2 + x 3 + . . . = 1 1 − x \large f(x)=1+x+x^2+x^3+…=\frac{1}{1-x} f(x)=1+x+x2+x3+…=1−x1
这又是为什么呢？
在母函数中， x x x作为形式参数，本身是没有意义的。
所以我们只要能找到一个函数代表它即可。
由于 1 1 − x \frac{1}{1-x} 1−x1的泰勒展开式为 1 + x + x 2 + x 3 + . . . 1+x+x^2+x^3+… 1+x+x2+x3+…，所以 f ( x ) = 1 1 − x f(x)=\frac{1}{1-x} f(x)=1−x1
拓展 f ‘ ( x ) = 1 + 2 x + 3 x 2 + 4 x 3 + . . . = 1 ( 1 − x ) 2 = ( 1 1 − x ) 2 = f 2 ( x ) \large f`(x)=1+2x+3x^2+4x^3+…=\frac{1}{(1-x)^2}=(\frac{1}{1-x})^2=f^2(x) f‘(x)=1+2x+3x2+4x3+…=(1−x)21=(1−x1)2=f2(x)
f ‘ ‘ ( x ) = 1 + 3 x + 6 x 2 + 10 x 3 + 15 x 4 . . . = 1 ( 1 − x ) 3 = f 3 ( x ) \large f“(x)=1+3x+6x^2+10x^3+15x^4…=\frac{1}{(1-x)^3}=f^3(x) f‘‘(x)=1+3x+6x2+10x3+15x4…=(1−x)31=f3(x)
推广 1 ( 1 − x ) k = ∑ i ∞ C i + k − 1 k − 1 x i = f k ( x ) \large \frac{1}{(1-x)^k}=\sum_{i}^{\infty} C_{i+k-1}^{k-1}x^i=f^k(x) (1−x)k1=∑i∞Ci+k−1k−1xi=fk(x)
用组合数学中的所谓“隔板法”求一下，第 i i i项的系数就是 C i + k − 1 k − 1 C_{i+k-1}^{k-1} Ci+k−1k−1
斐波那契通项公式
下面我们用生成函数求斐波那契数列的通项公式：
首先 f ( x ) = x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + . . . \large f(x)=x+x^2+2x^3+3x^4+5x^5+… f(x)=x+x2+2x3+3x4+5x5+…
将 f ( x ) f(x) f(x)乘上个 x x x，然后相减
f ( x ) − x ∗ f ( x ) = ( x + x 2 + 2 x 3 + 3 x 4 + . . . ) − ( x 2 + x 3 + 2 x 4 + 3 x 5 + . . . ) = x + x 3 + x 4 + 2 x 5 + 3 x 6 = x + x 2 f ( x ) \large f(x)-x*f(x)=(x+x^2+2x^3+3x^4+…)-(x^2+x^3+2x^4+3x^5+…)=x+x^3+x^4+2x^5+3x^6=x+x^2f(x) f(x)−x∗f(x)=(x+x2+2x3+3x4+…)−(x2+x3+2x4+3x5+…)=x+x3+x4+2x5+3x6=x+x2f(x)
解 f ( x ) f(x) f(x)得 f ( x ) = x 1 − x − x 2 f(x)=\frac{x}{1-x-x^2} f(x)=1−x−x2x
然后如何还原成序列呢？
先因式分解
x 1 − x − x 2 = x ( 1 − 1 − 5 2 x ) ( 1 − 1 + 5 2 x ) \large \frac{x}{1-x-x^2}=\frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)} 1−x−x2x=(1−21−5x)(1−21+5x)x
用裂项法 1 n ( n + k ) = 1 k ( 1 n − 1 n + k ) \frac{1}{n(n+k)}=\frac{1}{k}(\frac{1}{n}-\frac{1}{n+k}) n(n+k)1=k1(n1−n+k1)得
x ( 1 − 1 − 5 2 x ) ( 1 − 1 + 5 2 x ) = 1 ( 1 − 1 − 5 2 x ) ( ( 1 − 1 − 5 2 x + ( − 5 x ) ) x = 1 − 5 ( 1 1 − 1 − 5 2 x − 1 1 − 1 + 5 2 x ) = − 1 5 1 1 − 1 − 5 2 x + 1 5 1 1 − 1 + 5 2 x \large \frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}\\ \large=\frac{1}{(1-\frac{1-\sqrt{5}}{2}x)((1-\frac{1-\sqrt{5}}{2}x+(-\sqrt{5}x))}x\\ \large=\frac{1}{-\sqrt{5}}(\frac{1}{1-\frac{1-\sqrt{5}}{2}x}-\frac{1}{1-\frac{1+\sqrt{5}}{2}x})\\ \large=-\frac{1}{\sqrt{5}}\frac{1}{1-\frac{1-\sqrt{5}}{2}x}+\frac{1}{\sqrt{5}}\frac{1}{1-\frac{1+\sqrt{5}}{2}x} (1−21−5x)(1−21+5x)x=(1−21−5x)((1−21−5x+(−5x))1x=−51(1−21−5x1−1−21+5x1)=−511−21−5x1+511−21+5x1
把他分裂成等比数列的形式。
a n = − 1 5 ( 1 − 5 2 ) n + 1 5 ( 1 + 5 2 ) n \large a_n=-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n+\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n an=−51(21−5)n+51(21+5)n
这就是斐波那契数列通项公式。
终于写完了，接下来就是多刷例题训练了。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/200888.html原文链接：https://javaforall.net
