@Ivan_Anikin

Помогите с составлением алгоритма, оптимального по времени. У меня нет никаких конкретных идей кроме полного перебора.


В первой строке вводится целое число N — количество ожидающих покупателей (1 ⩽ N ⩽ 1000000). Вторая строка содержит N натуральных чисел (1 ⩽ a_i ⩽ 1000000). Выведите количество различных подпоследовательностей по модулю 1000000007 (10⁹ + 7). Подпоследовательностью {x_nk} называется числовая последовательность, которая составлена из членов последовательности {x_n} и в которой порядок следования ее элементов совпадает с их порядком следования в исходной последовательности {x_n}.

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Ввод:
4
1 2 1 3

Вывод:
13

В тесте из условия Михаил может найти следующие 13 различных подпоследовательностей:{1}, {1,1}, {1,1,3}, {1,2}, {1,2,1}, {1,2,1,3}, {1,2,3}, {1,3}, {2}, {2,1}, {2,1,3}, {2,3}, {3}.

0

Новичок

Ivan_Anikin, ссылка на задачу есть? У меня есть кое-какие идеи, но пока не могу четко их сформулировать. Буду еще думать, хотелось бы иметь возможность самому сдать задачу.

0

@Ivan_Anikin

https://olympiads.ru/moscow/20... ning.shtml Тур за 10 января, задача С.

0

Новичок

Так и не придумал решение. Только какие-то идеи есть. Вот чувствуется что здесь нужна простая динамика
dp[i] = количество уникальных подпоследовательностей которые заканчиваются числом a[i]
И вроде бы dp[i] = dp[0] + dp[1] + ... + dp[i-1] + 1, потому что мы тупо берем подпоследовательность которая заканчивается на a[0] и добавляем к ней a[i], подпоследовательность конец которой a[1] и дописываем a[i] и.т.д +1 потому что еще одна подпоследовательность которая состоит из одного числа a[i]. Но проблема в том, что числа могут повторяться(ну если б не повторялись ответ был бы 2ⁿ-1 ). И я никак не могу придумать как это учитывать. Я запутался. Мне кажется, что если у нас было скажем 1 2 3 4 2 5 и мы дошли до 5(dp[5]), мы должны суммировать не все числа до 5, двойку наверно не надо брать 2 раза, нужно прибавить dp[4] - только последнюю двойку, а первую не надо. И важно это все еще как-то быстро делать, за N log N хотя бы... Буду очень рад если кто-то расскажет как решать, редко тут на форуме задачи посложнее поиска минимума в массиве.

Добавлено через 2 минуты
Ну и если научиться считать dp[i] быстро и правильно, то для ответа останется только сложить все dp[i] но при этом если есть несколько одинаковых чисел a[i], то брать только то у которого dp[i] максимально. Тут либо сортировка поможет, либо map.

0