营员交流

.................................................................................................................生成函数的运算与应用金策杭州学军中学jcvb生成函数的运算与应用WC2015营员交流1/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)考虑一类组合对象组成的集合A，其中，每个元素a2A都被定义了“大小”jaj，它是一个非负整数。对于给定的n，大小为n的元素的数量是有限的，记作An。例：A是全体01串组成的集合，一个01串的大小被定义为它的长度，则An=2n。jcvb生成函数的运算与应用WC2015营员交流2/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)考虑一类组合对象组成的集合A，其中，每个元素a2A都被定义了“大小”jaj，它是一个非负整数。对于给定的n，大小为n的元素的数量是有限的，记作An。例：A是全体01串组成的集合，一个01串的大小被定义为它的长度，则An=2n。jcvb生成函数的运算与应用WC2015营员交流2/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)考虑一类组合对象组成的集合A，其中，每个元素a2A都被定义了“大小”jaj，它是一个非负整数。对于给定的n，大小为n的元素的数量是有限的，记作An。例：A是全体01串组成的集合，一个01串的大小被定义为它的长度，则An=2n。jcvb生成函数的运算与应用WC2015营员交流2/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)考虑一类组合对象组成的集合A，其中，每个元素a2A都被定义了“大小”jaj，它是一个非负整数。对于给定的n，大小为n的元素的数量是有限的，记作An。例：A是全体01串组成的集合，一个01串的大小被定义为它的长度，则An=2n。jcvb生成函数的运算与应用WC2015营员交流2/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)考虑一类组合对象组成的集合A，其中，每个元素a2A都被定义了“大小”jaj，它是一个非负整数。对于给定的n，大小为n的元素的数量是有限的，记作An。例：A是全体01串组成的集合，一个01串的大小被定义为它的长度，则An=2n。jcvb生成函数的运算与应用WC2015营员交流2/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)我们定义A(x)=∑n0Anxn为A的一般生成函数(OGF)。例：当A是全体01串时，A(x)=1+2x+4x2+8x3+


=112x形式幂级数，无需考虑级数在何时收敛。实际做题时往往只需处理级数的前n项系数(模一个大质数)。jcvb生成函数的运算与应用WC2015营员交流3/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)我们定义A(x)=∑n0Anxn为A的一般生成函数(OGF)。例：当A是全体01串时，A(x)=1+2x+4x2+8x3+


=112x形式幂级数，无需考虑级数在何时收敛。实际做题时往往只需处理级数的前n项系数(模一个大质数)。jcvb生成函数的运算与应用WC2015营员交流3/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)我们定义A(x)=∑n0Anxn为A的一般生成函数(OGF)。例：当A是全体01串时，A(x)=1+2x+4x2+8x3+


=112x形式幂级数，无需考虑级数在何时收敛。实际做题时往往只需处理级数的前n项系数(模一个大质数)。jcvb生成函数的运算与应用WC2015营员交流3/33..........................................................................................................一般生成函数(OrdinaryGeneratingFunction)我们定义A(x)=∑n0Anxn为A的一般生成函数(OGF)。例：当A是全体01串时，A(x)=1+2x+4x2+8x3+


=112x形式幂级数，无需考虑级数在何时收敛。实际做题时往往只需处理级数的前n项系数(模一个大质数)。jcvb生成函数的运算与应用WC2015营员交流3/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33..........................................................................................................最基本的运算有两类组合对象A和B，定义C为A和B的并集，（c是a或b）显然C(x)=A(x)+B(x)。O(n)计算。定义D为A和B的笛卡尔积，D的每个元素d都是A的某元素a与B的某元素b拼成的二元组(a;b)，其大小jdj定义为jaj+jbj，显然D(x)=A(x)B(x)。FFT乘法O(nlogn)。jcvb生成函数的运算与应用WC2015营员交流4/33