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