给出一根长度为N的杆子，你需要把它切成R段，这样每一段的长度都是正数，有多少种方法可以做到这一点？ [英] Given a rod of length N , you need to cut it into R pieces , such that each piece's length is positive, how many ways are there to do so?

问题描述

说明：

给定两个正整数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]

这篇关于给出一根长度为N的杆子，你需要把它切成R段，这样每一段的长度都是正数，有多少种方法可以做到这一点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！