计数与替换每k转

Question

问题如下：你有n类型的项目，你想选择它们的l（订单事项）。仅当自上次选择该项目以来选择了k其他项目时，才可以重新取样类型的项目。计算您可以形成的项目序列的总数。如果这令人困惑，以下示例将清除：

说n = 5，l = 6和k = 3。

答案是5 * 4 * 3 * 2 * 2 * 2。在第一个回合我们可以选择5个项目中的任何一个。在第二，第三和第四回合我们可以选择任何4，3和2剩余项目。然后，在第五个回合我们可以选择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)。