python - 每 k 圈更换计数

Question

问题如下:您有n 种类型的项目，您想要选择其中的l 种(顺序很重要)。仅当自上次选择该项目后选择了 k 个其他项目时，您才可以对该类型的项目重新采样。计算您可以形成的项目序列总数。如果这令人困惑，下面的示例将解决问题:

假设 n = 5、l = 6 和 k = 3。

答案是5 * 4 * 3 * 2 * 2 * 2。 在第一回合，我们可以选择 5 个项目中的任何一个。在第二、第三和第四轮，我们可以再次选择 4、3 和 2 剩余项目中的任何一个。然后，在第 5 轮我们可以选择 1，但也可以再次选择 5，因为自上次选择后还选择了 3 个其他项目，依此类推。所以总计数是 480。

这里有一个简单的算法来解决这个问题:

def differentPlaylists(n, k, l):
    ans, choices = 1, n
    while l > 0:
        ans = (ans * choices) % 1000000007
        choices -= 1
        k, l = k - 1, l - 1
        if k < 0: choices += 1
    return ans

这可行，但速度太慢。我想不通如何生成一种算法，用少于 l 乘法操作来解决这个问题。

谁能帮我弄清楚我该怎么做？

Answer 1

看来您只需要确切数字的余数。答案是:
(n!/(n-k)! * (n-k)^(l-k)) % M = (((n!/(n-k)!) % M) * ((n-k)^(l-k) % M)) % M。

您不需要循环来查找(n-k)^(l-k) % M，您可以使用exponentiation by squaring在 O(log(l-k)) 中有效。如果 k 足够小，它将使整体计算速度显着加快，因为此公式的第一个阶乘部分是在您的解决方案中以 O(k) 计算的。因此，在您的实现中，复杂度为 O(log(l-k)) + O(k) 而不是 O(l)。