给定一根长度为 N 的杆，你需要将它切成 R 段，使得每段的长度为正，有多少种方法可以做到这一点？

Question

描述：

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

示例：

N = 7，R = 3，有 15 种方法可以将长度为 7 的杆切成 3 段：(1,1,5) , (1,5,1), (5,1, 1) , (1,2,4) , (1,4,2) (2,1,4), (2,4,1) , (4,1,2), (4,2,1) , (1,3,3), (3,1,3), (3,3,1), (2,2,3), (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)

Answer 1

我从字面上翻译了 accepted answer of Ivaylo Strandjev here 的代码，它运行得更快：

def get_degree(n, p):# { // returns the degree with which p is in n!
    degree_num = 0
    u = p
    temp = n

    while (u <= temp):
        degree_num += temp // u
        u *= p
    return degree_num

def degree(a, k, p):
    res = 1
    cur = a

    while (k):
        if (k % 2):
            res = (res * cur) % p
        k //= 2
        cur = (cur * cur) % p
    return res


def CNKmodP( n, k, p):
    num_degree = get_degree(n, p) - get_degree(n - k, p)
    den_degree = get_degree(k, p)

    if (num_degree > den_degree):
        return 0

    res = 1
    for i in range(n, n - k, -1):
        ti = i
        while(ti % p == 0):
            ti //= p
        res = (res * ti) % p

    denom = 1
    for i in range(1, k + 1):
        ti = i
        while(ti % p == 0):
            ti //= p
        denom = (denom * ti) % p
    res = (res * degree(denom, p-2, p)) % p
    return res

要应用此方法，您只需调用

result = CNKmodP(n-1, r-1, 1000000007)

Answer 2

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

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]

Answer 3

在Java中我们可以使用BigInteger，因为我们计算的阶乘值可能不适合整数。此外，BigInteger 提供了内置方法乘法和除法。

static int CNRmodP(int N, int R, int P) {
    BigInteger ret = BigInteger.ONE;
    for (int i = 0; i < R; i++) {
        ret = ret.multiply(BigInteger.valueOf(N - i))
                .divide(BigInteger.valueOf(i + 1));
    }
    
    BigInteger p = BigInteger.valueOf(P);

    //Calculate Modulus
    BigInteger answer = ret.mod(p);
     
    //Convert BigInteger to integer and return it
    return answer.intValue();
}

要应用上述方法，您只需调用

    result = CNRmodP(N-1, R-1, 1000000007);

给定一根长度为 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?

python

math

combinations

permutation

dynamic-programming