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

Question

给定一个数组a的n整数,算多少序列(不连续也)有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

这就是子集和问题。

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

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。但这具有很高的复杂性：about O(n*S)，其中S是所有元素的总和。该dp数组还必须具有 size 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)，并且对于该问题是最优的。