078. 硬币分组(Coin partitions)

\(p(n)\)表示\(n\)个硬币分成不同的组的总的方法数。例如,五个硬币分组的方式刚好有七种,则\(p(5)=7\)。求使得\(p(n)\)整除一百万的最小的\(n\)值。

分析:这道题实际上和第七十六题是类似的,本质都是求整数分拆的方法数问题,区别主要在于:(1)这里求的分拆方法数比第七十六题的要多一,因为这里的分拆方法中包含这个数本身,而七十六题要求至少两个正整数;(2)这道题的数据规模要大得多,所以无法使用第七十六题中的动态规划方法加以解决,需要新的思路。实际上,在七十六题我所给的参考页面中,我们已经知道求解整数分拆数的方法除开动态规划外,还可以使用生成函数的方法,设\(p(n)\)表示数\(n\)拆分的方法数,则\(p(n)\)的生成函数为:

$$ {\displaystyle {\begin{aligned}\sum _{n\geq 1}p(n)z^{n}&={\frac {1}{(1-z)(1-z^{2})(1-z^{3})\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}} $$

最后一个等式的每一项的系数即为\(p(n)\),如\(p(0)=1,p(1)=1,p(2)=2\cdots,p(6)=11\)等等。从以上生成函数我们可以得到\(p(n)\)的如下递推关系:

$$ p\left( n \right) =\sum_{k=1}^n{\left( -1 \right) ^{k+1}\left( p\left( n-\frac{k\left( 3k-1 \right)}{2} \right) +p\left( n-\frac{k\left( 3k+1 \right)}{2} \right) \right)} $$

即为:

$$ p\left( n \right) =p\left( n-1 \right) +p\left( n-2 \right) -p\left( n-5 \right) -p\left( n-7 \right) +p\left( n-12 \right) +p\left( n-15 \right) -\cdots $$

很明显,此式中\((n-g_k)\)项就会变成负数,而我们定义\(p(n)=0(n<0)\),则之后的项不需要再做计算,如:

$$ p(9)=p(8)+p(7)-p(4)-p(2)+p(-3)+p(-6)=22+15-5-2+0+0=30 $$

根据以上递归式,如果需要计算\(p(n)\),我们只需要知道前\(2\sqrt{2n/3}\)项即可,如为了计算\(p(1000)\),我们只需要知道前五十项左右。因此,我们可以使用列表把已经求出的\(p(n)\)值缓存下来,这样在计算之后的\(p(n)\)值时可以直接使用。为了求得第一个整除一百万的\(p(n)\)值,我们从\(p(61)\)开始向上筛选,因为之前的值都小于一百万,不可能整除一百万。待筛选到满足要求的\(p(n)\)值时返回\(n\)值,即为题目所求。代码如下:

# time cost = 14.1 s ± 66.9 ms

def partion_function(n):
    pn = [1,1]
    for i in range(2,n+1):
        k,acc = 1,0
        g1 = lambda k : i - k*(3*k-1)//2
        g2 = lambda k : i - k*(3*k+1)//2
        f = lambda x : pn[x] if x >= 0 else 0
        while g1(k) >= 0:
            acc += (-1)**(k+1)*(f(g1(k))+f(g2(k)))
            k += 1
        pn.append(acc)
    return pn

def main(N=10**6):
    pn = partion_function(55400)
    for i in range(61,len(pn)):
        if pn[i] % N == 0:
            return i