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:
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