我的负面长度为N的数组A和正整数。我需要计算在这个阵列中加起来的数量多M（或0（MOD M）） 子集数 例如： 设A = {1,2,8,4,5}，M = 9， 然后，有4个这样的子集：

I have an array A of length N of negative as well as positive integers. I need to count the number of subsets in this array which add up to a multiple of a number M (or 0 (mod M)) For example: Let A = {1,2,8,4,5}, M = 9, Then, there are 4 such subsets:

我想生成所有可能的倍数，然后应用动态规划的子集之和，但限制不会允许我说。 约束： 1 =＆LT; N'LT = 10 ^ 5， 1 =＆LT; M＆LT; = 100， -10 ^ 9 =＆LT;阵列与其中的每一个条目; = 10 ^ 9

I thought of generating all possible multiples and then applying dynamic programming subset sum, but the constraints won't allow me that. Constraints: 1 =< N <= 10^5, 1 =< M <= 100, -10^9 =< each entry of array <=10^9

应该是什么我的做法对于这样的问题？

What should be my approach for this sort of problem?

推荐答案

您可以解决这个问题，通过动态规划，尽管广泛用于大型并购而迅速地为小M.对每个j满足0℃= J＆LT; = M -1，并且每个整数k满足0℃ K＆其中; = N时，令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 mod M）表示。当你遍历所有的j满足0℃= J＆LT; = M-1为每个k和再依次遍历所有K满足0℃= K＆LT; = N，你会得到你的答案在f（N，0 ）。总的复杂度为O（MN），这对于小M基本上是线性的N，最优的。

You can solve this problem by dynamic programming, albeit extensive for large M and fast for small M. For each j satisfying 0 <=j <= M-1, and each integer k satisfying 0 < k <= N, let f(k,j) be the number of subsets of array elements between 1 and k that add up to give a sum of j mod M. Then to extend the counter f(k,j) to f(k+1,j') for all j' you just need to take the (k+1)th element X in your sequence and set f(k+1,j') = f(k,j') + f(k,j' - X mod M). When you iterate over all j satisfying 0 <= j <= M-1 for each k and then successively iterate over all k satisfying 0 <= k <= N, you will get your answer at f(N,0). Total complexity is O(MN), which for small M is basically linear in N, optimal.