Нахождение количества подмножеств массива, которые складываются в кратные от определенного числа
У меня есть массив A длиной N как отрицательных, так и целых положительных чисел. Мне нужно посчитать количество подмножеств в этом массиве, которые складываются до кратного числа М (или 0 (мод М))
Например:
Пусть A = {1,2,8,4,5}, M = 9,
Тогда есть 4 таких подмножества:
- {}: Пустой набор, соответствующий кратному 0,
- {1,8}: соответствует кратному 9,
- {4,5}: соответствует кратному 9
- {1,8,4,5}: соответствует кратному 18.
Я думал о создании всех возможных кратных значений, а затем о применении суммы подмножеств динамического программирования, но ограничения не позволят мне этого.
Ограничения:
1 =< N <= 10 ^ 5,
1 =< M <= 100,
-10 ^ 9 =< каждая запись массива <= 10 ^ 9
Каким должен быть мой подход к такого рода проблемам?
Решение
Вы можете решить эту проблему с помощью динамического программирования, хотя и большого для большого M и быстрого для малого M. Для каждого j, удовлетворяющего 0 <= у <= M-1, и каждое целое число k удовлетворяет 0 < К <= 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 мод М). Когда вы перебираете все j, удовлетворяющие 0 <= j <= M-1 для каждого k и затем последовательно итерировать по всем k, удовлетворяющим 0 <= к <= N, вы получите ответ в точке f (N, 0). Общая сложность O (MN), которая для малых M в основном линейна по N, оптимальна.
Другие решения
Других решений пока нет …