交換ごとにkターン毎にカウント

Question

問題は次のとおりです。nタイプのアイテムがあり、そのうちのlを選択したい（発注事項）。最後にそのアイテムを選択してからk個の他のアイテムが選択されている場合にのみ、タイプのアイテムを再サンプリングすることができます。あなたが形成できるアイテムのシーケンスの総数を数えます。これが混乱している場合は、次の例を参照してください。

と言ってくださいn = 5,l = 6およびk = 3です。

答えは5 * 4 * 3 * 2 * 2 * 2です。 最初のターンで5つのアイテムのどれかを選択できます。 2回目、3回目、4回目に再び4、3、および2のいずれかのアイテムを選択できます。その後、5回目に1を選択することができますが、最後に選択された3つのアイテムが選択されたため、5が再度選択されます。総計は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(l)の代わりにO(log(l-k)) + O(k)の複雑さが発生します。