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

Question

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

现在我们必须检查是否可以从数组中选择一组数字，以便它们的总和可以被 M 整除，并输出"YES"或"NO"。

下面是两个示例：

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则问题陈述不会更改。让我们计算一下在除法后给出特定余数ja[i]元素的数量M.如果对于某些余数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 % 60, 2, 4
以布尔形式存储此信息{1, 0, 1, 0, 1, 0}

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

接下来，我们需要找到如果我们采用不同组的元素时可能出现的所有可能的子集。假设我们合并两个布尔余数数组a和b，如果我们能引入新的数组c，它将包含来自a和b子集的所有可能的元素余数和。朴素方法将要求我们在a上建立两个嵌套循环，b给O(M²)合并时间复杂度。

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

整体一致性是O(M²* log(M))，因为我们需要M这样的合并。