Сумма больших показателей 2

Question

Сумма больших показателей 2

Я пытаюсь выполнить задачу кодирования от hackerrank.com

Шашанк — новичок в математике, и он очень взволнован, узнав, что у данного количества элементов N есть (2^N — 1) непустой подсписок. Он записывает все непустые подсписки для данного набора A. Для каждого подсписка он вычисляет sublist_sum, который является суммой элементов, и обозначает их как S₁, S₂, S₃, … , S_(2^N-1).

Затем он определяет special_sum, P.

P = 2^S₁ + 2^S₂ + 2^S₃ …. + 2^{S_(2^N-1)} и сообщает P% (10 ^ 9 + 7).

Ouput Выведите значение special_sum, P по модулю (10 ^ 9 + 7).

Я почти уверен, что неправильно понял подсказку, но моя программа предназначена для получения списка номеров. Программа возьмет 2 в степень всех комбинаций этого списка (без дубликатов, порядок не имеет значения, всех размеров), затем сложит их все вместе и распечатает.

Пример с сайта

Список 1, 1, 2
Ouput 44

объяснение

{1} и 2 ^ 1 = 2

{1} и 2 ^ 1 = 2

{2} и 2 ^ 2 = 4

{1,1} и 2 ^ 2 = 4

{1,2} и 2 ^ 3 = 8

{1,2} и 2 ^ 3 = 8

{1,1,2} и 2 ^ 4 = 16

Итого будет 44;

Мое понимание простого суммирования показателей степени неверно, потому что ответ намного больше, чем ожидаемый ответ в первом тестовом примере (очевидно).

вход 422 412 417 497 284 Выход 67920854

По сути, я хочу, чтобы кто-то объяснил подсказку. Я думаю, что я просто рассчитываю частичную сумму, но я не знаю, когда или что я должен mod 10^9 + 7,

К вашему сведению, я только закончил Алгебру II, поэтому, если я пропустил математическую концепцию, помните мой опыт, когда вы мне это объясните. Я программировал на C ++, поэтому примеры кода на языке предпочтительнее.

Код Моя жалкая попытка найти решение: http://pastebin.com/c7YxCLMt

1

algebra algorithm c++

Решение

Другие решения

По сути, вопрос заключается в следующем: по заданному списку чисел найти сумму всех возможных произведений одного или нескольких элементов, где список — это не тот список, который вам дан, а два для этих полномочий. Ваш пример — сумма произведений одного или нескольких из {2, 2, 4}, например.

Мы можем упростить это далее, посмотрев на сумму произведений 0 или более элементов, а затем вычтя 1 для пустого продукта, который нам не нужен. Это позволяет вам использовать аккуратный трюк: для каждого элемента в списке вы умножаете либо на 1, либо на число. Таким образом, со списком {2, 2, 4} сумма равна (2 + 1) (2 + 1) (4 + 1) = 3 * 3 * 5 = 45, что дает 45 — 1 = 44 в качестве ответа.

Вот некоторый рабочий код в PARI / GP.

specialSum(v, m=10^9+7)=lift(factorback(apply(n -> Mod(2,m)^n+1, v))-1)

Использование:

specialSum([1,1,2])
specialSum([422,412,417,497,284])

2

Основываясь на комментариях выше, я думаю, что вы не совсем знакомы с этими алгоритмическими онлайн-судьями. Они не совпадают с реальными приложениями, они обычно имеют экстремальные ограничения, которые вынуждают вас использовать некоторые хитрые уловки, чтобы справиться с этим вовремя. (обычно ~ 1 секунда)

По этому вопросу проблему можно разделить на две части:

Как суммировать N^2 целые числа во времени, когда N <= 10^5? (за 1 секунду)
Как рассчитать 2^x % M где x <= 10^5*10^10 = 10^15 во время? (за 1 секунду)

И, конечно же, в процессе нельзя переполнить переменную, что является причиной того, что проблема просит вас вывести ответ MOD 10 ^ 9 + 7 (Я предполагаю, что вы знаете основные свойства модульной арифметики.)

Для пункта 1 ответ таков: ты не можешь Я пытаюсь сказать, что есть способ вычислить ответ без суммирования N ^ 2 пунктов. Я могу дать вам подсказку, основанную на моем принятом решении: Динамическое программирование, let DP (N) = необходимая сумма для элементов в массиве [0..N]. Если вы можете сформулировать повторение DP, вы можете получить ответ, только суммируя N целые числа, которые можно вычислить во времени.

Что касается пункта 2, вы не можете выполнять какие-либо наивные линейные предварительные вычисления (используйте цикл for и два раза из предыдущей итерации и т. Д.). Используя DP, упомянутый выше, вам нужно только рассчитать 2^x % M where x <= 10^10Тем не менее память и ограничение времени выполнения не удастся, если вы сделаете это. Здесь вам нужен еще один трюк под названием Возведение в степень по квадрату который может вычислить 2^n в O(lg n)и, таким образом, приемлемо.

Объедините обе точки 1 & 2, вы можете решить эту проблему Динамическое программирование & Возведение в степень по квадрату (& некоторая базовая модульная арифметика между ними).

0

Источник

Accepted Answer

Не видя вашей попытки, трудно сказать, что может быть недостатком, но две вещи приходят на ум как возможные подводные камни:

Вы упоминаете, что должны mod 10^9 + 7 но убедитесь, что вы делаете mod (10^9 + 7)
Числа, которые вы вычисляете (2 ^ 497, 2 ^ 284 и т. Д.): огромный и наверняка переполнится. Если вы уже не справляетесь с этим, вы можете улучшить свою попытку, попробовав что-то вроде того, что они делают. Вот.

Редактировать: После просмотра вашего кода, кажется, что вы столкнулись с проблемой переполнения. Вы извлечете пользу из включения идей Вот в ваше решение.

3