求解长度不超过k的所有子数组乘积之和的高效算法

存在时间复杂度为O(n log n)的分治解法，不受模数M是否为质数的限制，远优于你当前的O(nk)实现，具体思路如下：

核心思路：CDQ分治 #

我们将数组递归拆分为左右两个子段，总结果由三部分组成：

• 左子段内部所有符合要求的子数组乘积和
• 右子段内部所有符合要求的子数组乘积和
• 同时跨越左右子段的、长度小于等于k的子数组乘积和

前两部分可以递归求解，第三部分单独计算：

1. 先预处理右子段所有前缀的乘积，以及前缀乘积的前缀和数组，时间复杂度O(右子段长度)
2. 枚举左子段的后缀长度l（取值范围1~min(k-1, 左子段长度)），此时右子段最多可取长度为r = min(k - l, 右子段长度)的前缀
3. 每个l对应的贡献为：左子段长度为l的后缀乘积 * 右子段前r个前缀乘积的和，模M后累加到总结果即可

每一层递归的计算量为O(n)，总共有O(log n)层递归，整体时间复杂度为O(n log n)，空间复杂度为O(n)。

额外优化：O(n)线性解法（仅适用于M为质数的场景） #

如果题目给定的模数M是质数，我们可以借助前缀乘积+逆元实现线性时间求解：

• 定义前缀乘积数组pre，其中pre[0] = 1，pre[i] = (pre[i-1] * A[i-1]) % M
• 子数组A[j...i]的乘积可表示为 (pre[i+1] * inv(pre[j])) % M，其中inv是模M下的逆元
• 维护一个滑动窗口，窗口内的j满足i-j+1 <=k，累加所有合法的乘积值即可，时间复杂度O(n)

原有代码的问题 #

1. 使用了C++标准不支持的变长数组D[n][n]，n较大时会直接触发栈溢出，且空间复杂度高达O(n²)，完全没有必要
2. 递推方式效率极低，多余计算量过多

参考实现（分治版，适配所有模数场景） #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k, M;
vector<int> A;

long long solve(int l, int r) {
    if (l == r) {
        return A[l] % M;
    }
    int mid = (l + r) / 2;
    long long res = (solve(l, mid) + solve(mid + 1, r)) % M;
    
    // 计算跨左右的贡献
    vector<long long> pre_prod(r - mid, 0), pre_sum(r - mid, 0);
    pre_prod[0] = A[mid + 1] % M;
    pre_sum[0] = pre_prod[0];
    for (int i = 1; i < r - mid; i++) {
        pre_prod[i] = (pre_prod[i-1] * A[mid + 1 + i]) % M;
        pre_sum[i] = (pre_sum[i-1] + pre_prod[i]) % M;
    }
    
    long long left_prod = 1;
    for (int l_len = 1; l_len <= min(k-1, mid - l + 1); l_len++) {
        left_prod = (left_prod * A[mid - l_len + 1]) % M;
        int max_r_len = min(k - l_len, (int)pre_prod.size());
        if (max_r_len <= 0) break;
        res = (res + left_prod * pre_sum[max_r_len - 1]) % M;
    }
    return res % M;
}

int main() {
    cin >> n >> k >> M;
    A.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        A[i] %= M;
    }
    cout << solve(0, n-1) % M << endl;
    return 0;
}

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