algorithm - 计算给定 k 模和的子序列数

Question

给定一个包含 n 整数的数组 a，计算有多少子序列(也不是连续的)具有 sum % k = 0:

1 <= k < 100
1 <= n <= 10^6
1 <= a[i] <= 1000

O(n^2) 解决方案很容易实现，但是更快的方法是 O(n log n) 或 O(n) 是必需的。

Answer 1

这是 subset sum问题。

一个简单的解决方案是这样的:

s = 0
dp[x] = how many subsequences we can build with sum x 
dp[0] = 1, 0 elsewhere
for i = 1 to n:
    s += a[i]
    for j = s down to a[i]:
        dp[j] = dp[j] + dp[j - a[i]]

然后您可以简单地返回所有 dp[x] 的总和，使得 x % k == 0。虽然这具有很高的复杂性:大约 O(n*S)，其中 S 是所有元素的总和。 dp 数组还必须具有大小 S，您可能甚至无法为您的约束声明它。

更好的解决方案是首先不要迭代大于或等于 k 的总和。为此，我们将使用 2 个 dp 数组:

dp1, dp2 = arrays of size k
dp1[0] = dp2[0] = 1, 0 elsewhere
for i = 1 to n:
    mod_elem = a[i] % k
    for j = 0 to k - 1:
        dp2[j] = dp2[j] + dp1[(j - mod_elem + k) % k]

    copy dp2 into dp1

return dp1[0]

其复杂度为 O(n*k)，并且是该问题的最佳选择。