Это решение этой задачи было придумано однажды ночью при разработке совершенно другого контеста :)

Пусть - ответ задачи.

Тогда верен факт (например, можно доказать его из формулы включений-исключений)



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

Понятно, что такое решение у меня было, и очень хотелось увеличить ограничение по N раз в 20, чтобы его отсечь, однако не хотелось делать участникам, пишущим на Java, совсем-совсем плохо.

Представим, что мы честно, на листочке, хотим провести расчет по вышеуказанной формуле, например:



Стоп! Так считала наша программа, а не мы. Мы считали вот так:



Это толкает нас к следующей идее: будем представлять наше состояние на шаге j двумя массивами X_j и Y_j, имея ввиду



Причем на последнем шаге j = k будем иметь



А переход от шага j к шагу j + 1 выполняется по самой первой формуле с последующим слиянием отсчетов с одинаковым Y (массивы в любой момент поддерживаются сортированными, фактически производится слияние прошлого с обновлением и т.д.)

Сложность этого решения, будет, очевидно,

Утверждение.



Доказательство.

Любое число, попадающее в массив Y, имеет вид для некоторого натурального a. Заметим, что



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

Таким образом, сложность этого решения

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

Решение, написанное с оптимизацией хранения для маленьких отсчетов Y (можно посмотреть мои посылки) на сервере CF выполняется порядка 300мс на худшем тесте и укладывается в 2 секунды для N = 10¹⁵, k = 100 (т.е. решает задачу при ограничении на N два порядка больше)

Вопросы, предложения, пожелания?