Count number of subsequences with given k modulo sum

Question

Given an array a of n integers, count how many subsequences (non-consecutive as well) have sum % k = 0:

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

An O(n^2) solution is easily possible, however a faster way O(n log n) or O(n) is needed.

Answer 1

This is the subset sum problem.

A simple solution is this:

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]]

Then you can simply return the sum of all dp[x] such that x % k == 0. This has a high complexity though: about O(n*S), where S is the sum of all of your elements. The dp array must also have size S, which you probably can't even afford to declare for your constraints.

A better solution is to not iterate over sums larger than or equal to k in the first place. To do this, we will use 2 dp arrays:

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]

Whose complexity is O(n*k), and is optimal for this problem.