《普通型母函数初级教程 --by 晓露式泠》由会员分享，可在线阅读，更多相关《普通型母函数初级教程 --by 晓露式泠（4页珍藏版）》请在金锄头文库上搜索。
1、 普通型母函数初级教程普通型母函数初级教程-by 式泠（Bstring）这几天一直在做这一类的题目。看的教程主要是业余 ACmer 大神 TankyWoo 的个人博客以及一些母函数课件（稍后发上）。（ACMer 新手请先打开传送门 http:/ 的大作先，要理解如何生成一个普通型生成函数）再进 Tanky Woo 的传送门（http:/ 把 离 散 数 列 和 幂 级 数 一 一 对 应 起 来 ”（好好理解！）（PS：这里的幂级数不考虑收敛，故作 形式幂级数 ）接下来读懂模板中的数组 c1 和 c2 以及 i, j, k, 这三个变量的含义。请先暂时不管后面的细节，可以这样看 c1 和 c2
2、 的关系：c1 是个桶，c2 是个瓢，c2 舀水倒进 c1，不断的倒，直到 c1 满了。所以我才说 c1 应改为 answer，而 c2 应该为 current answer 或 temp。再在细节上理解 c1 和 c2 和 i， j， k先在纸上把依照题意抽象出的生成函数的多项式写出，比如这么一个多项式。其实这个模板就是模拟这个多项式的相乘过程，其实这里的 x 是浮云，所以我提议直接写成这样（0,1,2,3.) (0,2,4,6.) (0,3,6,9.)把指数这个 衣服 从 x 这个 晾衣架 下拿下来了多项式的相乘 对于指数来说就是相加。c1 数组在进入 i,j,k 的这个三重循环之前，有一
3、个很重要的初始化，c1 的部分元素被刷成了1，这些 1 代表了第一个括号里的（0,1,2,3.）这些 衣服 原来所挂衣架 x 的系数。下面进入很难理解的 i, j, k 三重循环。（洗把脸让脑袋清醒一下再看吧，孩纸们）用初中生的方法在纸上算一算（把省略号后面的数忽略吧）你可能会这样做：先乘前两个括号(木有数学公式插件，将就着看吧，主要得自己在纸上写)：1 * 1 + 1 * (x2) + 1 *(x4)+ x * 1 + x *(x2) + x * (x4)+ (x2) * 1 +(x2)*(x2) +(x2)*(x4)=（1+ x +2 (x2) + x3 + 2(x4) + x5 + x6
4、）然后再拿这个括号的每一项去乘上原式中的第三个括号（这里我就不再写了，累死，不过你要理解的话还真得在纸上写完去！）没错，边写边对照这个 for 循环。（聪明的孩纸应该已经看懂了）下面为了负责还是要面向一下普通大众（没看懂就继续往下看吧，这里木有人会笑你的）这里的变量 i 一般情况下 i 与乘式的状态有关，比如模板中的 i 从 2 开始，就是说先拿前两项相乘，还有重要的一点是 可以利用 i 控制乘式中指数的增量，这道题的增量控制太简单了，其他题目中的增量控制可能就要有些变化了。i 的最大值是整个多项式全部展开之后得到的最大指数，这个值一般可以通过题意得到或估算得到一个稍大的值。变量 j 是非常费
5、解的，真正理解可能要掌握 DP（动态规划）。按照 TankyWoo 的和Seagg 的讨论结果， j 应该指示的是前 i 个括号乘起来之后的第 j 个变量。注意 j 的 控制条件 是 整个多项式展开之后的 最小指数 到 最大指数 的范围，增量是 j+，不管题目怎么变，这个增量是不会变的。变量 k 比较好理解了，就是第 i 个括号里的每一项的指数了，控制条件一般有两个（这个模板只有一个）一个是 k 的上限控制， 不可超过第 i 个括号里的最大指数；一个是 j+k 的上限控制，不可超过 整个多项式全部展开之后得到的最大指数。核心的式子出现了 ! c2 j+k += c1j;好了，现在该看你的草稿纸
6、上的算式了，这个式子反映的就是你的乘式中指数相加的步骤。T H I N KKKKKKKKKKING NOOOOOOOOOOOOOW !接下来一直累加 c2，这个 j 的 for 循环终了之后， 进入到同层次的第二个 j 的 for 循环，到这一步，程序已经帮你算完了前两个式子的相乘过程， c2 这个瓢的水已经装满了，倒进 c1这个桶。程序又跳转到了下一个 i 的 for 循环了（其实你可以通过单步调试慢慢查看每一个变量的动态，个人认为这是理解循环代码的最佳途径。）如此反复，终于把这个多项式完全展开了，得到了每一个拥有不同指数的晾衣架 x 的系数。这个系数自然就是组合的方案数。套在乘法的马甲里，代表元素的指数做着加法运算，这就是组合计数的加法原理啊！（PS：第一次写教程，若有疏漏， 还望各位大牛指正， 新手也应该靠自己领悟为主，不要太依赖网上流传的各种教程。别老以为自己笨搞不了算法，那样的借口是在用你的惰性吞噬着你的智商！ ）
