algorithm - P 个元素的子集总和（允许重复）可被 M 整除

Question

给定一个包含N个元素的数组A。我们需要找到子集的数量（允许数字重复），使得子集中的元素数量为 P 并且这些 P 元素的总和可以被M整除。

N 可以达到10^5

P 最高可达10^5

M 可以达到10

数组中的元素最多可达10^9

我的想法：我想使用从 sum=M 到 sum=P*max(A) 的动态编程生成子集和，然后找到所有可被 M 整除的子集和，但这肯定效率太低。知道如何解决这个问题吗？

子集总和（允许重复）算法可以在这里看到：https ://tutorialspoint.dev/algorithm/dynamic-programming-algorithms/ways-sum-n-using-array-elements-repetition-allowed

即使是关于该方法的小提示也将不胜感激

标签： algorithmtime-complexitydynamic-programmingsubset-sum

Answer 1

提示：通常在这类问题中，检查约束是一个很好的方法。引起注意的是变量 M（最多 10 个）的约束。这意味着您可以使用模算术并找到大小为 P 且 M 余数为 0 的子集和的数量。