如何用滑动窗口高效计算数组k长度连续子数组乘积模p的值

核心思路 #

由于直接做除法模运算的前提是除数和模数互质，因此我们可以把数组元素中所有和模数p相关的质因子单独拆分统计，剩下的互质部分可以安全使用模运算+逆元做滑动窗口计算，时间复杂度为O(n * ω(p))，其中ω(p)是p的不同质因子个数，对于任意不超过1e18的p来说，ω(p)最多不超过15，完全可以视为线性复杂度。

具体步骤 #

1. 预处理模数p的质因数分解
   将p分解为p = q1^e1 * q2^e2 * ... * qm^em，其中q1~qm是不同的质数，e1~em是对应的指数。

边界情况：如果p=1，所有结果都为0，直接返回长度为n-k+1的全0数组即可。

2. 预处理数组每个元素的拆分结果
   对数组中每个元素a[i]，拆分出两部分：

• 对每个质因子qj，统计a[i]包含的qj的指数，记为cnt[i][j]
• 把a[i]中所有qj的因子全部除尽，得到和p互质的部分r[i]，对r[i]取模p存储

3. 滑动窗口计算结果
   初始化第一个长度为k的窗口的两个状态：

• 互质乘积模p的值：mul = (r[0] * r[1] * ... * r[k-1]) % p
• 每个质因子的总计数：total_cnt[j] = sum(cnt[0][j] ... cnt[k-1][j])

之后每滑动一次窗口：

• 移出左端元素a[left]：
  • mul = mul * 逆元(r[left]) % p （因为r[left]和p互质，逆元一定存在）
  • 对每个j，total_cnt[j] -= cnt[left][j]
• 移入右端元素a[right]：
  • mul = mul * r[right] % p
  • 对每个j，total_cnt[j] += cnt[right][j]
• 计算当前窗口的模p结果：
  检查所有total_cnt[j]是否都 >= e_j，如果是，结果为0；
  否则，计算extra = (q1^total_cnt[1] * q2^total_cnt[2] * ... * qm^total_cnt[m]) % p，结果为(mul * extra) % p

示例验证 #

对应你给出的例子：a = [3, 12, 5, 2, 3, 7, 4, 3]，k=3，p=12=2^2*3^1
预处理后的r数组为[1, 1,5,1,1,7,1,1]，cnt数组对应2、3的指数分别为：
3: [0,1]、12: [2,1]、5:[0,0]、2:[1,0]、3:[0,1]、7:[0,0]、4:[2,0]、3:[0,1]
第三个窗口是[5,2,3]，total_cnt为[1,1]，2的总计数1小于要求的2，所以不为0。extra=2^1 *3^1=6，mul=5*1*1=5，结果为5*6 mod12=6，和示例结果一致。

优势 #

• 全程所有运算都在模p下进行，不会出现超大数，完全避免溢出和大数运算耗时问题
• 不需要p为质数，也不需要数组元素和p互质，适配所有正整数p的场景
• 时间复杂度接近线性，适用于超大长度数组的计算

内容的提问来源于stack exchange，提问作者Fish_n_Chips