Сумма подмножеств P элементов (с разрешенным повторением), делимая на M

Question

Имеется массив A из N элементов. Нам нужно найти количество подмножеств (с разрешением повторение чисел), чтобы количество элементов в подмножестве было P, а сумма этих P элементов делится на M .

N может быть до 10 ^ 5

P может быть до 10 ^ 5

M может быть до 10

Элементы в массиве могут содержать до 10 ^ 9

Что я подумал: я подумал о генерации суммы подмножеств с использованием динамического c запуска программы от суммы = M до суммы = P * max (A), а затем найдите все суммы подмножеств, которые делятся на M, но, несомненно, будут слишком неэффективными. Любая идея, как я могу решить эту проблему?

Алгоритм суммы подмножества (с разрешенным повторением) можно увидеть здесь: https://tutorialspoint.dev/algorithm/dynamic-programming-algorithms/ways-sum-n-using-array-elements-repetition-allowed

Даже небольшие подсказки о подходе цениться

Answer 1

Подсказка: Обычно в такого рода задачах рекомендуется проверять ограничения. Внимание привлекает ограничение для переменной M (до 10). Это означает, что вы можете работать с модульной арифметикой c и найти количество подмножеств суммы P, которые имеют остаток 0 с M.