Recherche du nombre de sous-ensembles d’un tableau qui s’ajoutent à un multiple d’un nombre spécifique

J’ai un tableau A de longueur N de nombres entiers négatifs et positifs. J’ai besoin de compter le nombre de sous-ensembles dans ce tableau qui totalisent un multiple d’un nombre M (ou 0 (mod M))
Par exemple:

Soit A = {1,2,8,4,5}, M = 9,
Ensuite, il y a 4 tels sous-ensembles:

  • {}: Ensemble vide, correspondant au multiple de 0,
  • {1,8}: correspondant au multiple 9,
  • {4,5}: correspondant au multiple 9
  • {1,8,4,5}: correspondant au multiple de 18.

J’ai pensé générer tous les multiples possibles puis appliquer une sum de sous-ensemble de programmation dynamic, mais les contraintes ne me le permettent pas.

Contraintes:
1 = <N <= 10 ^ 5,
1 = <M <= 100,
-10 ^ 9 = <chaque entrée du tableau <= 10 ^ 9

Quelle devrait être mon approche pour ce genre de problème?

Vous pouvez résoudre ce problème par une programmation dynamic, même étendue pour les grands M et rapide pour les petits M. Pour chaque j satisfaisant 0 <= j <= M-1, et chaque entier k satisfaisant 0