以下内容引用自frkstyc’s Blog, 原文地址:
http://www.blog.edu.cn/user2/frkstyc/archives/2006/1180760.shtml
——————————————————-我是分隔线——————————————————
有人曾经在POJ webboard上声称生成函数是“没用的东西”。但这个题却是利用生成函数解决问题的一个很好的例子。
题目的大意是有不超过5种重量在10以内的糖果（不同的糖果可以有相同重量），给一个整数P<= 1015，要求一个最小的重量w，只得做一个重量为w的糖果盒的不同方法数至少是P。
看到P的规模就可以立即否决普通的动态规划解法。容易联想到的算法是二分法，但这个题乍看之下没有明显的单调性。尝试用生成函数解决。为描述方便，以下直接用一个实例来说明。
假设有3种糖果，重量分别为2, 3, 5。用生成函数中xn项的系数表示做重量为n的糖果盒的方法数，那么对应的生成函数就是
f(x) = 1 / ((1 – x2)(1 – x3)(1 – x5))。
这个形式是没有办法直接利用的，因为里面三个因子的展开式都有无穷项，要直接找系数的通项公式也不容易。但是利用一个很简单的技巧就可以解决这两个问题。（应当说明，这个技巧虽然看起来很简单，但的确是要费一番思考的。）注意到2, 3, 5的最小公倍数[2, 3, 5] = 30，因此将上面的式子改写一下，变成
g(x) = ((1 – x30) / (1 – x2)) ((1 – x30) / (1 – x3)) ((1 – x30) / (1 – x5))，
h(x) = 1 / (1 – x30)3，
f(x) = g(x) h(x)。
这样，g(x)是一个一般的多项式，h(x)虽然有无穷项但形式很规整，f(x)只是g(x)和h(x)的乘积。
g(x)只需直接展开即可，展开的结果是一个次数小于3 * 30 = 90次的多项式。对于h(x)，为方便起见，作一个换元，记
h’(y) = 1 / (1 – y)3。
通过计算或者查阅工具书可以知道h’(y)中yn项的系数为组合数C(3 – 1, n + 3 – 1)，其中的3就是h’(y)的解析式中1 – y的次数。因此h(x)中x30 n的次数也是C(3 – 1, n + 3 – 1)，而其他项的系数都是0。
综合上面的讨论，可以得到计算f(x)中xn项的系数的方法。记p(x)中xn项的系数为c(p, n)。对于n< 90，c(f, n)可以直接利用动态规划或者限制次数地直接展开f(x)得到。（注意：这个不是c(g,n)！）对于n >= 90，记n = 30 k + r，其中0 <= r < 30，那么根据f(x) = g(x) h(x)，有以下公式
c(f, n) = C(2, k + 2) c(g, r) + C(2, k + 1) c(g, r + 30) + C(2, k) c(g, r + 60)。
和f(x)直接相关的计算已经基本解决。剩下求最小的问题，方法还是二分法。虽然从整体看，c(f,n)关于n不一定是单调的，但是假如把n写成n = 90 k + r，其中0 <= r < 90，就可以发现对固定的r，c(f, 90 k + r)关于k是单调的。因此只需枚举r，对k应用二分法，然后从所有候选的n = 90k + r中选取最小的即可。