c++ - 查找加起来等于特定数字倍数的数组子集的数量

Question

我有一个长度为 N 的数组 A，其中包含负整数和正整数。我需要计算此数组中子集的数量，这些子集加起来是数字 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 =< N <= 10^5,
1 =<中号 <= 100,
-10^9 =<数组的每一项<=10^9

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

Answer 1

你可以通过动态规划来解决这个问题，尽管对于大 M 是广泛的，对于小 M 是快速的。对于满足 0 <= j <= M-1 的每个 j，以及满足 0 < k <= N 的每个整数 k，让f(k,j) 是 1 和 k 之间的数组元素的子集数，它们相加得到 j mod M 的总和。然后将计数器 f(k,j) 扩展为 f(k+1,j' ) 对于所有 j' 你只需要在你的序列中获取第 (k+1) 个元素 X 并设置 f(k+1,j') = f(k,j') + f(k,j' - X模 M)。当您对每个 k 迭代所有满足 0 <= j <= M-1 的 j，然后连续迭代所有满足 0 <= k <= N 的 k 时，您将在 f(N,0) 处得到答案。总复杂度为 O(MN)，对于较小的 M 基本上与 N 呈线性关系，最优。