查找数组的子集数，这些子集加起来是特定数字的倍数

Question

我有一个数组A，长度为N，包括负整数和正整数。我需要计算这个数组中的子集数量，这些子集加起来是数字 M（或 0 （mod M））
的倍数例如：

设 A = {1,2,8,4,5}， M = 9，
然后，有 4 个这样的子集：

• {}：空集，对应于倍数 0，
• {1,8}：对应于倍数 9，
• {4,5}：对应于倍数 9
• {1,8,4,5}：对应于倍数 18。

我想生成所有可能的倍数，然后应用动态规划子集和，但约束不允许我这样做。

约束：
1 =<= 10^5，
1 =<= 100，
-10^9 =<数组的每个条目><=10^9

对于这类问题，我应该采取什么方法？

Answer 1

你可以通过动态编程来解决这个问题，尽管对于大 M 来说很广泛，对于小 M 来说速度很快。对于每个满足 0 <=j <= M-1 的 j 和满足 0 <= N 的每个整数 k，设 f（k，j） 是 1 和 k 之间的数组元素子集的数量，加起来得到 j mod M 的总和。然后，要将计数器 f（k，j） 扩展到所有 j' 的 f（k+1，j'），您只需要将序列中的第 （k+1） 个元素 X 设置为 f（k+1，j'） = f（k，j'） + f（k，j' - X mod M）。当你迭代所有满足 0 的 j <= j <= M-1 对于每个 k 然后依次迭代所有满足 0 <= k <= N 的 k 时，你会得到 f（N，0） 的答案。总复杂度为 O（MN），对于小 M 在 N 中基本上是线性的，最优。