(HDUACM2010版_08)母函数

1、ACM计程仪编程，杭州电子科技高等院校刘春英，2020/7/27，2，2010年，省赛情况，报告，2020/7/27，3，每周一(7) :若考虑chennen以下的多项式乘法，x2项系数a1a2 a1a3 . an-1an中的所有项同样地，x-3项的系数以包括取来自n个元素体a-1、a-2、a-n的3个元素组合的全体的方式进行类推。 设(81 )、2020/7/27、6、a1=a2=an=1，则在(8-1)式中按照a1a2 a1a3 . an-1an项的系数，对于特性：2020/7/27、7、母函数定义：系列a0、a1、a2 如果系列a0、a1和a2已知，则可以根据定义给出对应的父函数G(x

2、)。 相反，如果已经获得了序列的父函数G(x )，则也确定该序列。 可以标记为序列a0、a1、a2、an。2020/7/27、9、9、实例分析、2020/7/27、10、例1:1克、2克、3克、4克的砝码各1张，可以说是什么重量？ 各有几个可能的方案？ 怎么解决这个问题呢？ 考虑结构母函数。 对于以x的指数来表示的重量，一克的平衡可以用函数1 x表示，一克的平衡可以用函数1 x2表示，一克的平衡可以用函数1 x3表示，一克的平衡可以用函数1 x4表示，2020/7/27、11，等等=(1xx2x3) (1x3x4x7)=1xx 22 x 32 x 42x52 x6x7x8x9x 10由以上函数

3、可知：从1克到右端为2 x 5项，即5克的方案与2:5=3 2=4 1相同，6=1 2 3=4 2。 十等于十二三四。 因此，6克的方案是2，10克的方案是1，2020/7/27，12，例2:1分、2分、3分的邮票贴出不同的数值求出方案数，邮票允许重复，因此母函数是：以展开后的x4为例，即4=111=12=13=2。 把整数分解成若干整数和(相当于把n个不分性别的球放入n个不含标识牌的框中，其中该框把允许空的整数分割成若干整数和，方法不同，所以把不同分割方法的总数称为分割得分。 2020/7/27，14，练习(写下列问题的母函数):例3 :如果平衡锤有1克3张，平衡锤有2克4张，平衡锤有4克2

4、张，可以说是什么重量？ 各有几种方案？ 例如，将4:整数n分割成1，2，3，m的和，并求其母函数。 例5 :如果在上面的例子中m至少出现一次，那么其母函数如何，2020/7/27，15，如何编写计程仪程序来实现母函数的应用，核心问题，牛鼻子：多项式展开，以2020/7/27，16，整数分割为例：观察以下母函数实际的计程仪编程：让计算机用自己的思维方法改正即可，/authorbylwg # includeusingnamespacestd； const int lmax=10000； 英特尔c2lmax 1、c2lmax 1。 进入主()进入，I，j，k； 我的意思是，我的意思是，I=0； i=n； i ) c1i=0； c2i=0； for (i=0； i=n； i ) c1i=1； for (i=2； i=n； (j=0； j=n； j )for