滑动window算法计算一个数组模p的所有k元素连续子数组积的列表
Sliding window algorithm to calculate the list of all k-element contiguous subarray products of an array modulo p
我有一个 n 正整数数组。我想计算大小为 k 模 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]
我们可以使用滑动 window 轻松计算 k_products。我们所要做的就是计算第一个 k 大小的子数组的乘积，然后使用以下公式计算 k_product 的下一个元素：
k_product[i] = k_product[i - 1] * a[i + k] / a[i - 1]
在形成整个列表后，我们可以为每个 i 计算 k_product[i] % p 以获得 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不会溢出，但处理非常大的数字会很耗时。
这不是一个滑动window算法，但它是一个简单有效的解决这个问题的方法，在O(n)时间内没有任何划分：
设 A 为您的原始数组。我们假设在 A 的每个第 k 个元素上都有一个“标记”——元素 A[0]、A[k]、A[2k] 等。这确保了 A 中的每个 k-length window将包含恰好一个标记。
现在，创建两个新数组 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-length window的完整乘积，因为任意window的乘积来自A[i]...A[i+ k-1] 只是 B[i] * C[i+k-1]。请记住 window 中只有一个标记。 B[i]是标记前元素的乘积，C[i+k-1]是标记后元素与标记后元素的乘积
我有一个 n 正整数数组。我想计算大小为 k 模 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]
我们可以使用滑动 window 轻松计算 k_products。我们所要做的就是计算第一个 k 大小的子数组的乘积，然后使用以下公式计算 k_product 的下一个元素：
k_product[i] = k_product[i - 1] * a[i + k] / a[i - 1]
在形成整个列表后，我们可以为每个 i 计算 k_product[i] % p 以获得 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不会溢出，但处理非常大的数字会很耗时。
这不是一个滑动window算法，但它是一个简单有效的解决这个问题的方法，在O(n)时间内没有任何划分：
设 A 为您的原始数组。我们假设在 A 的每个第 k 个元素上都有一个“标记”——元素 A[0]、A[k]、A[2k] 等。这确保了 A 中的每个 k-length window将包含恰好一个标记。
现在，创建两个新数组 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-length window的完整乘积，因为任意window的乘积来自A[i]...A[i+ k-1] 只是 B[i] * C[i+k-1]。请记住 window 中只有一个标记。 B[i]是标记前元素的乘积，C[i+k-1]是标记后元素与标记后元素的乘积