algorithm - DP解决方案查找是否存在可被M整除的一组数字

Question

假设我们有数字 N，这样 0 < N <= 10^6 和 2 <= M <= 10^3 以及 N 个元素数组 a[1], a[2], ... a[ N] (0<= a[i] <=10^9)\

现在我们必须检查是否可以从数组中选择一组数字，使得它们的和可以被 M 整除，并输出"is"或“否”。

这里有两个例子:

N = 3, M =5 a={1,2,3} answer="YES"

N = 4, M = 6 a={3,1,1,3} answer="YES"

提前致谢。

Answer 1

C++ 解决方案。

//declare dp array of boolean values of size M
bool dp[M] = {0}; // init with fasle values
for(int i = 0; i < N; i++) {
    bool ndp[M] = {0}; // init temporary boolean array
    ndp[a[i] % M] = 1; // add a subset with one a[i] element
    for(int j = 0; j < M; j++) 
        if(dp[j]) { // if we may find a subset of elements with sum = j (modulo M)
            ndp[j] = 1; // copy existing values
            ndp[(j + a[i]) % M] = 1; // extend the subset with a[i], which will give a sum = j + a[i] (modulo M)
        }
    // copy from ndp to dp before proceeding to the next element of a
    for(int j = 0; j < M; j++) dp[j] = ndp[j];
}

//check dp[0] for the answer

算法复杂度将为 O(N*M)，在您的情况下为 O(10⁹)

编辑:添加 ndp[a[i] % M] = 1; 行以使 dp[j] 变为非零值。

---

可能还有另一种选择 O(M * M * log(M) + N) 解决方案，在您的情况下是 O(10⁷)(但有大常数)。

请注意，如果将每个 a[i] 替换为 a[i] % M，问题陈述不会改变。让我们计算在 M 上除法后给出特定余数 j 的 a[i] 元素的数量。如果对于一些余数 j 我们在 a 中找到了 k 元素，那么我们可以生成以下子集总和(可能会产生唯一的余数)

j, 2 * j % M, 3 * j % M ... k * j % M

示例:设 M = 6，对于剩余的 2，我们在 a 中找到了 5 个元素。然后我们有以下子集的唯一总和:

2 % 6, 2 * 2 % 6, 3 * 2 % 6, 4 * 2 % 6, 5 * 2 % 6
这是 0, 2, 4
以 bool 形式存储此信息 {1, 0, 1, 0, 1, 0}

我们最多有 M 个这样的组，它们产生 M 大小的 bool 可能余数数组。

接下来我们需要找到所有可能出现的子集，如果我们将采用不同组的元素。假设我们合并两个 bool 余数数组 a 和 b 如果我们可以引入新数组 c 将包含子集中所有可能的元素余数和a 和 b。天真的方法将要求我们在 a 和 b 上进行两个嵌套循环，从而给出 O(M²) 合并时间复杂性。

我们可以使用快速傅立叶变换算法将复杂度降低到O(M * log(M))。每个 bool 数组都有一个多项式Σ a_i*xⁱ，其中系数a_i 取自 bool 数组。如果我们想合并两个数组，我们可以将它们的多项式相乘。

整体复杂度为 O(M² * log(M))，因为我们需要进行 M 次这样的合并。