115. 方格组合计数II(Counting block combinations II)

用灰色方块和最短长度为\(m\)的红色方块摆成长度为\(n\)的一行,要求任意两个红色方块(长度可以不同)之间至少有一个灰色方块。我们用填充计数函数\(F(m, n)\)代表符合上述要求的填充方法数。例如,\(F(3, 29) = 673135\)以及\(F(3, 30) = 1089155\)

也就是说,当\(m = 3\)时,可以看出\(n = 30\)是使得填充计数函数首次超过一百万的最小值。同样地,当\(m = 10\)时,可以验证\(F(10, 56) = 880711\)以及\(F(10, 57) = 1148904\),因此\(n = 57\)是使得填充计数函数首次超过一百万的最小值。

求当\(m = 50\)时,求使得摆法计数函数首次超过一百万的最小\(n\)值。

注:这是第114题一个更难的版本。

分析:使用我们在第114题中推导出来的递推关系式,这道题的解法是显然的。唯一需要注意是,我们的计数函数与题目中的计数函数\(n,m\)的顺序是相反的,在写代码中加以注意即可:

# time cost = 19.8 µs ± 80.8 ns

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,m):
    if n < m:
        return 1
    elif n == m:
        return 2
    else:
        return 2*f(n-1,m)-f(n-2,m)+f(n-m-1,m)

def main(N=10**6):
    n = 51
    while True:
        w = f(n,50)
        if w > N:
            return n
        else:
            n += 1