给定 k 和 sum，计算满足模 sum 余数为 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)。

- dorado

---

由于您指定了恒定的上限，因此您问题的任何解决方案都是平凡的O(1)。 - John Coleman

哈哈 :) 那很好!! @JohnColeman - vish4071

@JohnColeman 这可能是一些在线评测问题。他们告诉你上限和时间限制，以便让你了解你的解决方案应该具有什么复杂度，才能在给定的上限时间内运行。 - IVlad

@JohColeman 哈哈，不错.. :D - dorado

@vish4071 是的，我确定它是子序列而不是子数组。 - dorado

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

然后你可以简单地返回所有x％k==0的dp[x]之和。但这个算法复杂度很高：大约是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)，在解决这个问题时是最优的。

- IVlad

Answer 2

有一个时间复杂度为O(n + k^2 lg n)的算法。计算输入数组模k的直方图c(0), c(1), ..., c(k-1)（即有c(r)个元素是r模k的）。然后计算

  k-1
product (1 + x^r)^c(r) mod (1 - x^k)
  r=0

如下所示，其中减少多项式的常数项是答案。

我们不是使用快速指数方法评估每个因子，然后相乘，而是将事情倒过来。如果所有都为零，则答案为1。否则，递归地评估。

      k-1
P = product (1 + x^r)^(floor(c(r)/2)) mod (1 - x^k).
      r=0

然后计算

      k-1
Q = product (1 + x^r)^(c(r) - 2 floor(c(r)/2)) mod (1 - x^k),
      r=0

通过利用因子的稀疏性，在时间上以 O(k^2) 的速度进行后续计算。结果是 P^2 Q mod (1 - x^k)，通过朴素卷积在时间上以 O(k^2) 的速度计算。

- David Eisenstat

Answer 3

遍历数组 a，计算 a[i] mod k 的个数；应该有 k 种这样的计数。

递归并记忆 k, 2*k, 3*k ... 的不同分区，部分小于或等于 k，添加相应计数的乘积。

例如，如果 k 是 10，一些分区将是 1+2+7 和 1+2+3+4。但在记忆过程中，我们只需要计算一次数组中有多少对数 mod k 等于 (1 + 2)。

例如，k = 5，a = {1,4,2,3,5,6}：

counts of a[i] mod k: {1,2,1,1,1}

products of distinct partitions of k:
  5   => 1
  4,1 => 2
  3,2 => 1

products of distinct partitions of 2 * k with parts <= k:
  5,4,1   => 2
  5,3,2   => 1
  4,1,3,2 => 2

products of distinct partitions of 3 * k with parts <= k:
  5,4,1,3,2 => 2

answer = 11

  {1,4} {4,6} {2,3} {5}
  {1,4,2,3} {1,4,5} {4,6,2,3} {4,6,5} {2,3,5}
  {1,4,2,3,5} {4,6,2,3,5}

- גלעד ברקן