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

甚至对该方法的一些小提示都将不胜感激

Answer 1

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