温州网站开发app制作,discuz下载官网,微博营销的优势和劣势,绍兴关键词排名工具参考文章#xff1a; 生成函数(母函数)——目前最全的讲解 《小学生都能看懂的生成函数从入门到升天教程》《生成函数全家桶》 Acwing 进阶课程–生成函数
引入
任意给定一个无限长的序列a0,a1....an....a_{0},a_{1}....a_{n}....a0,a1....an.... 定义函数g(x)a0x0a1x…参考文章 生成函数(母函数)——目前最全的讲解 《小学生都能看懂的生成函数从入门到升天教程》《生成函数全家桶》 Acwing 进阶课程–生成函数
引入
任意给定一个无限长的序列a0,a1....an....a_{0},a_{1}....a_{n}....a0,a1....an.... 定义函数g(x)a0x0a1x1a2x2...anxn...g(x)a_{0}x^{0}a_{1}x^{1}a_{2}x^{2}...a_{n}x^{n}...g(x)a0x0a1x1a2x2...anxn... 这是一个无穷级数一般设x的取值范围为-1x1。显然这个无穷级数收敛我们可以在x取向正无穷时得到该无穷级数的值 我们称这个函数g(x)为序列的生成函数 我们不难看出 这么讲太抽象了看一些例题就知道了
例题
例题1 砝码问题
有三个砝码分别是1g2g3g求用这三个砝码一共能凑出多少个不同重量并求每个重量的组成方案
用生成函数来解决这个问题 我们将这个问题拆分成几个独立的子问题然后利用乘法原理计算。在本题中利用乘法原理来考虑每个砝码的选择方式。 在生成函数中乘法原理可以映射到多项式乘法 对于每个砝码有选和不选两个方式 1个1g砝码可以看作是f1x0x1f1x^0x^1f1x0x1,x0x^0x0表示不取(重量为0)x1x^1x1表示只取一个 1个2g砝码可以看作是f2x0x2f2x^0x^2f2x0x2,x0x^0x0表示不取x2x^2x2表示只取两个 1个3g砝码可以看作是f3x0x3f3x^0x^3f3x0x3,x0x^0x0表示不取x3x^3x3表示只取三个 那么生成函数就是每个方案数的乘积 g(x)f1∗f2∗f3(1x1)∗(1x2)∗(1x3)1xx22x3x4x5x6g(x)f1*f2*f3(1x^1)*(1x^2)*(1x^3)1xx^22x^3x^4x^5x^6g(x)f1∗f2∗f3(1x1)∗(1x2)∗(1x3)1xx22x3x4x5x6 最终算式中的1xx22x3x4x5x61xx^22x^3x^4x^5x^61xx22x3x4x5x6就说明了0g的方案是13g的方案是2sss克的方案数就是axsax^saxs的系数a指数表示重量系数表示方案数
例题2砝码升级版
有三个砝码分别是1g(共两个)2g(无数个)3g(共一个)求凑出4g重量的组成方案数 生成函数 f1(1xx2)f1(1xx^2)f1(1xx2) f2(1x2x4x6......)f2(1x^2x^4x^6......)f2(1x2x4x6......) f3(1x3)f3(1x^3)f3(1x3) ff1∗f2∗f3(1xx2)∗(1x2x4x6......)∗(1x3)ff1*f2*f3(1xx^2)*(1x^2x^4x^6......)*(1x^3)ff1∗f2∗f3(1xx2)∗(1x2x4x6......)∗(1x3) 凑出4g重量的组成方案数有 1,x4,11 ,x^4,11,x4,1 x,1,x3x,1,x^3x,1,x3 x2,x2,1x^2,x^2,1x2,x2,1 一共有三个方案x4x^4x4的系数是3
例题3苹果选择
现在有n种苹果每种苹果无限个问选k个苹果的方案数
方法一隔板法
我们先不用生成函数用组合数来做 我们设第i种苹果选了xi个那么有∑i1nxik,xi0\sum_{i1}^{n}x_{i}k,x_{i}0∑i1nxik,xi0 我们用隔板法来做需要xi大于0x_{i}大于0xi大于0 我们令aixi1a_{i}x_{i}1aixi1 有∑i1naikn,ai0\sum_{i1}^{n}a_{i}kn,a_{i}0∑i1naikn,ai0 这个我们可以看作是有kn个小球现在有n个桶必须保证每个桶至少有一个球方案数为Ckn−1n−1C_{kn-1}^{n-1}Ckn−1n−1 ∑i1naikn,ai0\sum_{i1}^{n}a_{i}kn,a_{i}0∑i1naikn,ai0方程组解的个数就是方案数 隔板法讲解 这是隔板法的模板做法就是看作有n-1个隔板kn个球有kn-1个间隙将这个n-1个隔板插入到kn-1个间隙中这样就会分割出n个空间,每个空间至少有一个小球。方案数就是kn-1个间隙中选出n-1个位置放隔板Ckn−1n−1C_{kn-1}^{n-1}Ckn−1n−1 方法二生成函数
f1(1x1x2x3....)1−xn1−x11−x,n取向无穷大f1(1x^1x^2x^3....)\frac{1-x^{n}}{1-x}\frac{1}{1-x},n取向无穷大f1(1x1x2x3....)1−x1−xn1−x1,n取向无穷大 f211−xf2\frac{1}{1-x}f21−x1 … ff1∗f2∗...∗fn1(1−x)na0a1∗x...akk..∑k∞Ckn−1n−1xkff1*f2*...*fn\frac{1}{(1-x)^n}a_{0}a_{1}*x...a_{k}^k..\sum_{k}^{∞}C_{kn-1}^{n-1}x^{k}ff1∗f2∗...∗fn(1−x)n1a0a1∗x...akk..k∑∞Ckn−1n−1xk 我们刚才用隔板法求出每种方案数 所以akCkn−1n−1a_{k}C_{kn-1}^{n-1}akCkn−1n−1
总结
生成函数大多用来解决有限或者无线物品的组合方案 生成函数⇔原问题分解为若干个子问题⇔求每个子问题的生成函数⇔所有子问题生成函数乘起来就是总方案数生成函数\Leftrightarrow原问题分解为若干个子问题\Leftrightarrow求每个子问题的生成函数\Leftrightarrow所有子问题生成函数乘起来就是总方案数生成函数⇔原问题分解为若干个子问题⇔求每个子问题的生成函数⇔所有子问题生成函数乘起来就是总方案数
生成函数常用公式
高等数学基本上都学过
普通型生成函数
单下标序列普通型生成函数
A(x)∑n0∞anxnA(x)\sum_{n0}^{∞}a_{n}x^nA(x)n0∑∞anxn
双下标序列普通型生成函数
A(x1,x2)∑n0∞a(n,m)x1nx2mA(x_{1},x_{2})\sum_{n0}^{∞}a_{(n,m)}x_1^nx_2^mA(x1,x2)n0∑∞a(n,m)x1nx2m
普通型生成函数常用公式
11−x∑i0∞xi\frac{1}{1-x}\sum_{i0}^{∞}x^i1−x1i0∑∞xi
指数型生成函数
二项式定理:
(xy)n∑i1nCniaibn−i(xy)^n\sum_{i1}^{n}C_{n}^ia^ib^{n-i}(xy)ni1∑nCniaibn−i (x1)n∑i0nCnixi(x1)^{n}\sum_{i0}^{n}C_{n}^ix^i(x1)ni0∑nCnixi 1(1−x)n∑i0∞Cni−1ixi\frac{1}{(1-x)^n}\sum_{i0}^{∞}C_{ni-1}^{i}x^{i}(1−x)n1i0∑∞Cni−1ixi
例题
HDU1028 HDU1085 洛谷P2000 BZOJ3028
