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

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

Шашанк — новичок в математике, и он очень взволнован, узнав, что заданный l мощности N имеет (2N - 1) непустой подсписок. Он записывает все непустые подсписки для заданного множества A. Для каждого подсписка он вычисляет sublist_sum, представляющую собой сумму элементов, и обозначает их S1, S2, S3, ..., S(2N-1).

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

P = 2S1 + 2S2 + 2S3 .... + 2S(2N-1) и сообщает P % (10^9 + 7) .

OUPUT Вывести special_sum, P по модулю (10^9 + 7).

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

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

Список 1, 1, 2 Вывод 44

Пояснение

  1. {1} и 2^1 = 2
  2. {1} и 2^1 = 2
  3. {2} и 2^2 = 4
  4. {1,1} и 2^2 = 4
  5. {1,2} и 2^3 = 8
  6. {1,2} и 2^3 = 8
  7. {1,1,2} и 2^4 = 16

Таким образом, всего будет 44;

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

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

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

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

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


c++ algorithm algebra
person MyLone Trojan    schedule 15.08.2016    source источник
comment
объясните подсказку. Какой? Уверяю вас, что 2 в 422-й степени будет намного, намного больше, чем 67920854. Первая часть этого вопроса довольно разборчива; но на полпути он как бы падает с обрыва... И полное исключение минимально воспроизводимого примера бесполезно , либо.   -  person Sam Varshavchik    schedule 15.08.2016
comment
Мне жаль. Я действительно не знаю, куда обратиться. Моя проблема концептуальна, поэтому мой исходный код бесполезен. добавлю полную подсказку   -  person MyLone Trojan    schedule 15.08.2016
comment
К сожалению, stackoverflow.com не предназначен для обсуждения концептуальных проблем. Но, скорее, для конкретных технических вопросов и ответов.   -  person Sam Varshavchik    schedule 15.08.2016
comment
Что ты посоветуешь?   -  person MyLone Trojan    schedule 15.08.2016
comment
Часть проблемы заключается в том, чтобы выяснить, как понять проблему. 2^422 — смехотворно большое число. Вы не можете вычислить его с помощью простых операций. Таким образом, задача состоит в том, чтобы увидеть, сможете ли вы понять, как «реструктурировать математику», чтобы вы могли предоставить простое вычислительное решение. Это не будет вашей проблемой, если кто-то другой решит ее за вас. ;)   -  person Disillusioned    schedule 15.08.2016
comment
Модуль суммы есть сумма модулей. (4 + 4) по модулю 3 = 2 = 4 по модулю 3 + 4 по модулю 3. Итак, вы знаете, как вычислить по модулю из 2 ^ N по модулю XXX, а затем суммировать, и это простая задача.   -  person Severin Pappadeux    schedule 15.08.2016
comment
мн... интересная задачка. Возможно, это поможет? en.wikipedia.org/wiki/Fermat%27s_little_theorem, если 10^9 + 7 на самом деле простое число, тогда, возможно, вы могли бы как-то упростить свой список подсписков. Если исходный список может содержать до 10 ^ 5 элементов, генерировать все подсписки — глупая затея.   -  person TuanDT    schedule 15.08.2016

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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

person Jaquez    schedule 15.08.2016

arrow_upward
2
arrow_downward

По сути, вопрос заключается в следующем: по списку чисел найдите сумму всех возможных произведений одного или нескольких элементов, где список — это не тот список, который вам дали, а два в этих степенях. Например, ваш пример представляет собой сумму произведений одного или нескольких из {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])
person Charles    schedule 15.08.2016
comment
Это работает для другого набора чисел в вопросе? 422 412 417 497 284? - person smac89; 15.08.2016
comment
@ smac89 Да, это так. Не забудьте сначала возвести эти числа в степень двойки, как описано в моем первом абзаце. - person Charles; 15.08.2016
comment
@MyLoneTrojan Максимально просто: для каждого числа n вычислите 2 в степени n плюс один. Перемножьте все эти числа вместе и вычтите 1. - person Charles; 15.08.2016
comment
@MyLoneTrojan Но, вероятно, вам сначала нужно знать, как вычислять модульное сложение, умножение и возведение в степень. В противном случае вам придется работать с огромными числами, и это, вероятно, потребует еще больше усилий. - person Charles; 15.08.2016
comment
так что ... 2 ^ N мод (10 ^ 9 + 7) + 1 для каждого числа? - person MyLone Trojan; 15.08.2016
comment
@MyLoneTrojan Да. Затем добавьте 1 к каждому, затем умножьте их все (mod 10^9+7), затем вычтите 1. - person Charles; 15.08.2016
comment
@MyLoneTrojan Я добавил некоторый код (краткий), чтобы показать, что идея работает как для примера, так и для фактического вопроса. Он проходит за доли секунды. - person Charles; 15.08.2016
comment
Как вы узнали, как упростить? Вы можете дать ссылку на какую-нибудь теорему или доказательство? - person MyLone Trojan; 15.08.2016
comment
@MyLoneTrojan Мой пост является доказательством - я не видел этого раньше, я только что разобрался. - person Charles; 15.08.2016
comment
Я не понимаю, почему вы прибавляете и вычитаете на единицу - person MyLone Trojan; 15.08.2016
comment
@MyLoneTrojan Добавление 1 включает или не включает каждый фактор. Если вы расширите (2 + 1) (2 + 1) (4 + 1), вы получите 8 продуктов, и вы пытаетесь получить сумму всех из них, кроме наименьшего, который равен 1. Вычитание 1 избавляет того, что. Смотрите мой второй абзац. - person Charles; 15.08.2016
comment
Давайте продолжим обсуждение в чате. - person MyLone Trojan; 15.08.2016

arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

person shole    schedule 15.08.2016