我有一個n正整數陣列。我想計算一個大小k為 modulo的所有連續子陣列乘積的串列p。例如對于以下陣列：
a = [3, 12, 5, 2, 3, 7, 4, 3]
同k = 3和p = 12，所有的有序串列k尺度的連續子陣列產品將是：
k_products = [180, 120, 30, 42, 84, 84]
和模p我們有：
k_products_p = [0, 0, 6, 6, 0, 0]
我們可以k_products使用滑動視窗輕松計算。我們所要做的就是計算第一個k大小的子陣列的乘積，然后k_product使用以下公式計算下一個元素：
k_product[i] = k_product[i - 1] * a[i k] / a[i - 1]
在形成整個串列后，我們可以計算k_product[i] % p每個i得到k_product_p。就是這樣。O(n)復雜度還不錯。
但是如果 的元素a[i]很大， k_product 的元素可能會溢位，因此我們無法計算k_product_p。另外，例如，我們不能執行以下操作：
k_product[i] = ((k_product[i - 1] % p) * (a[i k] % p) / (a[i - 1] % p)) % p // incorrect
那么有沒有一種快速的演算法來做到這一點？請注意，p不一定是素數，也不一定是 的元素的互質數a。
編輯：如評論中所述，python 中不會溢位，但處理非常大的數字將非常耗時。
uj5u.com熱心網友回復：
這不是滑動視窗演算法，但它是在 O(n) 時間內解決此問題的一種簡單有效的方法，無需任何除法：
讓 A 成為您的原始陣列。我們將想象在 A 的每個第 k 個元素上都有一個“標記”——元素 A[0]、A[k]、A[2k] 等。這確保了 A 中的每個 k 長度的視窗將恰好包含一個標記。
現在，創建兩個新陣列 B 和 C，使得：
在陣列 B 中，每個元素 B[i] 將包含 A[i] 和所有后續元素的乘積（mod p），直到但不包括下一個標記。如果 A[i] 被標記，則 B[i] = 1。您可以從 i=n-1 到 i=0 一次反向計算。
在陣列 C 中，每個元素 C[i] 將包含 A[i] 和所有前面的元素的乘積（mod p），直到并包括前一個標記。如果標記了 A[i]，則 C[i] = A[i]。您可以在從 i=0 到 i=n-1 的單次傳遞中進行計算。
現在，您可以輕松地在恒定時間內計算任何 k 長度視窗的完整乘積，因為來自 A[i]...A[i k-1] 的任何視窗的乘積只是B[i] * C[ i k-1]。請記住，視窗內只有一個標記。B[i]是標記前元素的乘積，C[i k-1]是被標記元素與其后元素的乘積。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340403.html