给出一根长度为N的杆子,你需要把它切成R段,这样每一段的长度都是正数,有多少种方法可以做到这一点?

问题描述

说明:

给定两个正整数N和R,有多少种不同的方法可以将一根长度为N的杆切成R段,使得每段的长度都是正整数?输出此答案的模数为1,000,000,007。

示例:

在N=7和R=3的情况下,有15种方法将长度为7的棒切成3块:(1,1,5),(1,5,1),(1,2,4),(1,4,2)(2,1,4),(4,1,2),(4,2,1),(4,2,1),(1,3,3),(3,1,3),(3,3,1),(2,2,3),(2,3,2),(3,2,2),(3,2,2),(3,2,2),(2,3,2),(3,2,2)。

约束:

1 <= R <= N <= 200,000

测试用例:

 N    R       Output
 7    3           15
36    6       324632
81   66    770289477
96   88    550930798

我的方法:

我知道答案是(N-1 choose R-1) mod 1000000007。我尝试了所有不同的方法来计算它,但总是有10个测试用例中有7个超过了时间限制。这是我的代码,谁能告诉我还能用什么其他方法在O(1)时间复杂度内做到这一点。

from math import factorial

def new(n, r):
    D = factorial(n - 1) // (factorial(r - 1) * factorial(n - r))
    return (D % 1000000007)

if __name__ == '__main__':
    N = [7, 36, 81, 96]
    R = [3, 6, 66, 88]
    answer = [new(n, r) for n,r in zip(N,R)]
    print(answer)

解决方案

我认为问题需要您利用两个大的优化。第一种是缓存factorial()的中间值,以节省大批量(大T)的计算工作量。第二个优化是递增地减少你的值mod1000000007,这样你的数字保持很小,乘法保持恒定的时间。我已经更新了下面的示例,以使用自定义函数和itertools.accumulate预先计算阶乘表,而不是仅仅在递归实现中缓存调用(这将消除您所看到的递归深度问题)。

from itertools import accumulate

MOD_BASE = 1000000007
N_BOUND = 200000

def modmul(m):
    def mul(x, y):
        return x * y % m
    return mul
    
FACTORIALS = [1] + list(accumulate(range(1, N_BOUND+1), modmul(MOD_BASE)))

def nck(n, k, m):
    numerator = FACTORIALS[n]
    denominator = FACTORIALS[k] * FACTORIALS[n-k]
    return numerator * pow(denominator, -1, m) % m

def solve(n, k):
    return nck(n-1, k-1, MOD_BASE)

针对示例运行此命令:

>>> pairs = [(36, 6), (81, 66), (96, 88)]
>>> print([solve(n, k) for n, k in pairs])
[324632, 770289477, 550930798]

相关文章