每 k 圈更换计数

Question

问题如下：您有 n 种商品，您想要 select l 种商品（订单很重要）。仅当自上次您 select 对该项目进行 select 后还有 k 其他项目时，您才可以对某一类型的项目重新取样。计算您可以形成的项目序列总数。如果这令人困惑，下面的示例将解决问题：

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

答案是5 * 4 * 3 * 2 * 2 * 2。在第一回合，我们可以选择 5 个项目中的任何一个。在第二、第三和第四回合，我们可以再次选择 4、3 和 2 剩余项目中的任何一个。然后，在第五回合我们可以选择 1，但也可以再次选择 5，因为自上次选择以来还有 3 个其他物品 select，依此类推。所以总计数是 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，您可以使用在 O(log(l-k)) 中有效的 exponentiation by squaring。如果 k 足够小，它将使整体计算速度显着加快，因为此公式的第一个阶乘部分是在您的解决方案中的 O(k) 中计算的。因此，在您的实现中，复杂度是 O(log(l-k)) + O(k) 而不是 O(l)。

每 k 圈更换计数

Counting with Replacement Every k Turns

python

algorithm

combinatorics